  


Regularity in mixedinteger convex representability
Miles Lubin(mlubinmit.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 subfamily. 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 ) Citation: Download: [PDF] Entry Submitted: 06/15/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  