Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover
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