aussois_header.png

Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover
Robert Hildebrand  1@  , Adrian G¨oß  2  
1 : Virginia Tech [Blacksburg]
2 : Technische Universität Nürnberg

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.



  • Poster
Personnes connectées : 2 Vie privée | Accessibilité
Chargement...