  


Mixedinteger linear representability, disjunctions, and Chvatal functions  modeling implications
Amitabh Basu (basu.amitabhjhu.edu) Abstract: Jeroslow and Lowe gave an exact geometric characterization of subsets of $\mathbb{R}^n$ that are projections of mixedinteger linear sets, also known as MILPrepresentable or MILPR sets. We give an alternate algebraic characterization by showing that a set is MILPR {\em if and only if} the set can be described as the intersection of finitely many {\em affine Chvatal inequalities} in continuous variables (termed AC sets). These inequalities are a modification of a concept introduced by Blair and Jeroslow. Unlike the case for linear inequalities, allowing for integer variables in Chvatal inequalities and projection does not enhance modeling power. We show that the MILPR sets are still precisely those sets that are modeled as affine Chvatal inequalites with integer variables. Furthermore, the projection of a set defined by affine Chvatal inequalites with integer variables is still an MILPR set. We give a sequential variable elimination scheme that, when applied to a MILPR set yields the AC set characterization. This is related to the elimination scheme of Williams and WilliamsHooker, who describe projections of integer sets using \emph{disjunctions} of affine Chvatal systems. We show that disjunctions are unnecessary by showing how to find the affine Chvatal inequalities that cannot be discovered by the WilliamsHooker scheme. This allows us to answer a longstanding open question due to Ryan (1991) on designing an elimination scheme to represent finitelygenerated integral monoids as a system of \ch inequalities \emph{without} disjunctions. Finally, our work can be seen as a generalization of the approach of Blair and Jeroslow, and Schrijver for constructing consistency testers for integer programs to general AC sets. Keywords: mixedinteger linear representability; variable elimination; chvatal functions Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: [PDF] Entry Submitted: 12/20/2016 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  