Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929492090421248 |
|---|---|
| author | Hildebrand, Robert Göß, Adrian |
| author_facet | Hildebrand, Robert Göß, Adrian |
| contents | We study the complexity of identifying the integer feasibility of reverse convex sets. We present various settings where the complexity can be either NP-Hard or efficiently solvable when the dimension is fixed. Of particular interest is the case of bounded reverse convex constraints with a polyhedral domain. We introduce a structure, \emph{Boundary Hyperplane Cover}, that permits this problem to be solved in polynomial time in fixed dimension provided the number of nonlinear reverse convex sets is fixed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_05308 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover Hildebrand, Robert Göß, Adrian Optimization and Control We study the complexity of identifying the integer feasibility of reverse convex sets. We present various settings where the complexity can be either NP-Hard or efficiently solvable when the dimension is fixed. Of particular interest is the case of bounded reverse convex constraints with a polyhedral domain. We introduce a structure, \emph{Boundary Hyperplane Cover}, that permits this problem to be solved in polynomial time in fixed dimension provided the number of nonlinear reverse convex sets is fixed. |
| title | Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.05308 |