Mixed-integer linear representability, disjunctions, and Chvátal functions -- modeling implications

DOI10.1287/MOOR.2018.0967MaRDI QIDQ5108241zbMATH OpenOpenAlexFDO

Authors Amitabh Basu, Christopher Thomas Ryan, Guanyi Wang, Kipp Martin

Publication date 30 April 2020

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.07028

zbMATH Keywords

Chvátal functionsmixed-integer linear representabilitymodeling with integers

Mathematics Subject Classification ID

Mathematical modeling or simulation for problems pertaining to operations research and mathematical programming (90-10) Boolean programming (90C09) Mixed integer programming (90C11)

Abstract: Jeroslow and Lowe gave an exact geometric characterization of subsets of $mathbb{R}^n$ that are projections of mixed-integer linear sets, also known as MILP-representable or MILP-R sets. We give an alternate algebraic characterization by showing that a set is MILP-R {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 MILP-R 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 MILP-R set. We give a sequential variable elimination scheme that, when applied to a MILP-R set yields the AC set characterization. This is related to the elimination scheme of Williams and Williams-Hooker, 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 Williams-Hooker scheme. This allows us to answer a long-standing open question due to Ryan (1991) on designing an elimination scheme to represent finitely-generated integral monoids as a system of Chvatal 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.

Recommendations

• Mixed-integer linear representability, disjunctions, and variable elimination
• Representability in mixed integer programming. I: Characterization results
• Mixed-integer convex representability
• Mixed-integer convex representability
• Mixed-integer bilevel representability

Cites work

• Decomposing finitely generated integral monoids by elimination
• Fourier's Method of Linear Programming and Its Dual
• Fourier-Motzkin elimination extension to integer programming problems
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1349588 (Why is no real title available?)
• scientific article; zbMATH DE number 4119933 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• Integer Programming
• Integer programming as projection
• Integer programming duality: Price functions and sensitivity analysis
• Maximal lattice-free convex sets in linear subspaces
• Mixed integer linear programming formulation techniques
• Mixed-integer convex representability
• Mixed-integer linear representability, disjunctions, and variable elimination
• Modelling with integer variables
• On the Mixed Binary Representability of Ellipsoidal Regions
• Projecting systems of linear inequalities with binary variables
• Some properties of convex hulls of integer points contained in general convex sets
• The b-hull of an integer program
• The Elimination of Integer Variables
• The value function of an integer program

Cited in

(3)

• Mixed-integer linear representability, disjunctions, and variable elimination
• Modelling with integer variables
• Mixed-integer convex representability

This page was built for publication: Mixed-integer linear representability, disjunctions, and Chvátal functions -- modeling implications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5108241)