Mixed-Integer Linear Representability, Disjunctions, and Chvátal Functions—Modeling Implications
| Autor: | Kipp Martin, Guanyi Wang, Christopher Thomas Ryan, Amitabh Basu |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Mathematics of Operations Research. 44:1264-1285 |
| ISSN: | 1526-5471 0364-765X |
| DOI: | 10.1287/moor.2018.0967 |
| Popis: | Jeroslow and Lowe gave an exact geometric characterization of subsets of [Formula: see text] 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 if and only if the set can be described as the intersection of finitely many affine Chvátal 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 Chvátal 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 Chvátal inequalites with integer variables. Furthermore, the projection of a set defined by affine Chvátal inequalites with integer variables is still a 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 disjunctions of affine Chvátal systems. We show that disjunctions are unnecessary by showing how to find the affine Chvátal inequalities that cannot be discovered by the Williams–Hooker scheme. This allows us to answer a long-standing open question due to Jennifer Ryan on designing an elimination scheme to represent finitely-generated integral monoids as a system of Chvátal inequalities without disjunctions. Finally, our work can be seen as a generalization of the approach of Blair and Jeroslow and of Schrijver for constructing consistency testers for integer programs to general AC sets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|