Complexity of Integer Programming in Reverse Convex Sets via Boundary Hyperplane Cover

2024/09/09 by Hildebrand, Robert, Göß, Adrian
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2409.05308

Abstract

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, 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.

Related

• Complexity of linear relaxations in integer programming
• Convex quadratic sets and the complexity of mixed integer convex quadratic programming
• Algorithmic and Complexity Results for Cutting Planes Derived from Maximal Lattice-Free Convex Sets
• Minkowski's Convex Body Theorem and Integer Programming
• Intersection disjunctions for reverse convex sets