Mixed-integer convex representability

Abstract

We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number of possible integer assignments is finite. We develop a characterization for the more general case of unbounded integer variables together with a simple necessary condition for representability which we use to prove the first known negative results. Finally, we study representability of subsets of the natural numbers, developing insight towards a more complete understanding of what modeling power can be gained by using convex sets instead of polyhedral sets; the latter case has been completely characterized in the context of mixed-integer linear optimization.

References in corpus (2)

• Extended Formulations in Mixed-integer Convex Programming
• Mixed-integer convex representability

Cited by in corpus (6)

• Outer Approximation With Conic Certificates For Mixed-Integer Convex Problems
• Mixed-integer convex representability
• Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
• Mixed-integer convex representability
• Mixed-integer linear representability, disjunctions, and Chvatal functions --- modeling implications
• A mixed-integer branching approach for very small formulations of disjunctive constraints