Optimization Online


Regularity in mixed-integer convex representability

Miles Lubin(mlubin***at***mit.edu)
Ilias Zadik(izadik***at***mit.edu)
Juan Pablo Vielma(jvielma***at***mit.edu)

Abstract: Characterizations of the sets with mixed integer programming (MIP) formulations using only rational linear inequalities (rational MILP representable) and those with formulations that use arbitrary closed convex constraints (MICP representable) were given by Jeroslow and Lowe (1984), and Lubin, Zadik and Vielma (2017). The latter also showed that even MICP representable subsets of the natural numbers can be more irregular than rational MILP representable ones, unless certain rationality is imposed on the formulation. In this work we show that for MICP representable subsets of the natural numbers, a cleaner version of the rationality condition from Lubin, Zadik and Vielma (2017) still results in the same periodical behavior appearing in rational MILP representable sets after a finite number of points are excluded. We further establish corresponding results for compact convex sets, the epigraphs of certain functions with compact domain and the graphs of certain piecewise linear functions with unbounded domains. We then show that MICP representable sets that are unions of an infinite family of convex sets with the same volume are unions of translations of a finite sub-family. Finally, we conjecture that all MICP representable sets are (possibly infinite) unions of homothetic copies of a finite number of convex sets.

Keywords: Mixed integer nonlinear programming; Mixed integer programming formulations; Mixed integer representability

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 06/15/2017
Entry Accepted: 06/16/2017
Entry Last Modified: 06/15/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society