Mixed-Integer Convex Representability

Miles Lubin (), Juan Pablo Vielma () and Ilias Zadik ()
Additional contact information
Miles Lubin: Google Research
Juan Pablo Vielma: Google Research; Sloan School of Management, Massachussetts Institute of Technology, Cambridge, Massachussetts 02142
Ilias Zadik: Operations Research Center, Massachussetts Institute of Technology, Cambridge, Massachussetts 02142; Center for Data Science, New York University, New York, New York, 10011

Mathematics of Operations Research, 2022, vol. 47, issue 1, 720-749

Abstract: Motivated by recent advances in solution methods for mixed-integer convex optimization (MICP), we study the fundamental and open question of which sets can be represented exactly as feasible regions of MICP problems. We establish several results in this direction, including the first complete characterization for the mixed-binary case and a simple necessary condition for the general case. We use the latter to derive the first nonrepresentability results for various nonconvex sets, such as the set of rank-1 matrices and the set of prime numbers. Finally, in correspondence with the seminal work on mixed-integer linear representability by Jeroslow and Lowe, we study the representability question under rationality assumptions. Under these rationality assumptions, we establish that representable sets obey strong regularity properties, such as periodicity, and we provide a complete characterization of representable subsets of the natural numbers and of representable compact sets. Interestingly, in the case of subsets of natural numbers, our results provide a clear separation between the mathematical modeling power of mixed-integer linear and mixed-integer convex optimization. In the case of compact sets, our results imply that using unbounded integer variables is necessary only for modeling unbounded sets.

Keywords: Primary 90C11; 90C25; Convex MINLP; MIP Representability; MIP Formulations (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1146 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:1:p:720-749

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().