×
Basu, Amitabh; Martin, Kipp; Ryan, Christopher Thomas; Wang, Guanyi

Mixed-integer linear representability, disjunctions, and Chvátal functions – modeling implications. (English) Zbl 1434.90101

Math. Oper. Res. 44, No. 4, 1264-1285 (2019).
Summary: R. G. Jeroslow and J. K. Lowe [Math. Program. Study 22, 167–184 (1984; Zbl 0554.90081)] 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 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 C. E. Blair and R. G. Jeroslow [Math. Program. 23, 237–273 (1982; Zbl 0482.90068)]. 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 H. P. Williams [J. Comb. Theory, Ser. A 21, 118–123 (1976; Zbl 0326.90047)] and H. P. Williams and J. N. Hooker [Discrete Optim. 22, Part B, 291–311 (2016; Zbl 1387.90146)], 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 [J. Ryan, Linear Algebra Appl. 153, 209–217 (1991; Zbl 0743.90080)] 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 [loc. cit.] and of A. Schrijver [Theory of linear and integer programming. Chichester: John Wiley & Sons Ltd. (1986; Zbl 0665.90063)] for constructing consistency testers for integer programs to general AC sets.

Cited in 1 Document

MSC:

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

Keywords:

mixed-integer linear representability; Chvátal functions; modeling with integers

Citations:

Zbl 0554.90081; Zbl 0482.90068; Zbl 0326.90047; Zbl 1387.90146; Zbl 0743.90080; Zbl 0665.90063
Cite Review PDF
Full Text: DOI arXiv

References:

[1] [1] Balas E (2011) Projecting systems of linear inequalities with binary variables. Ann. Oper. Res. 188(1):19-31.Crossref, Google Scholar · Zbl 1254.90116 · doi:10.1007/s10479-009-0623-3
[2] [2] Barvinok A (2002) A Course in Convexity, Graduate Studies in Mathematics, vol. 54 (American Mathematical Society, Providence, RI).Google Scholar · Zbl 1014.52001
[3] [3] Basu A, Conforti M, Cornuéjols G, Zambelli G (2010) Maximal lattice-free convex sets in linear subspaces. Math. Oper. Res. 35(3):704-720.Link, Google Scholar · Zbl 1218.90130
[4] [4] Basu A, Martin K, Ryan CT, Wang G (2017) Mixed-integer linear representability, disjunctions, and variable elimination. Eisenbrand F, Koenemann J, eds. International Conference on Integer Programming and Combinatorial Optimization. IPCO 2017, Lecture Notes in Computer Science, vol. 10328 (Springer, Cham, Switzerland), 75-85.Crossref, Google Scholar · Zbl 1418.90173 · doi:10.1007/978-3-319-59250-3_7
[5] [5] Blair CE, Jeroslow RG (1982) The value function of an integer program. Math. Programming 23(1):237-273.Crossref, Google Scholar · Zbl 0482.90068 · doi:10.1007/BF01583794
[6] [6] Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming, Graduate Texts in Mathematics, vol. 271 (Springer, Cham, Switzerland).Google Scholar · Zbl 1307.90001
[7] [7] Del Pia A, Poskin J (2016) On the mixed binary representability of ellipsoidal regions. Louveaux Q, Skutella M, eds. International Conference on Integer Programming and Combinatorial Optimization. IPCO 2016, Lecture Notes in Computer Science, vol. 9682 (Springer, Cham, Switzerland), 214-225.Crossref, Google Scholar · Zbl 1419.90075 · doi:10.1007/978-3-319-33461-5_18
[8] [8] Dey SS, et al.. (2013) Some properties of convex hulls of integer points contained in general convex sets. Math. Programming 141(1/2):507-526.Crossref, Google Scholar · Zbl 1300.90018 · doi:10.1007/s10107-012-0538-7
[9] [9] Jeroslow RG, Lowe JK (1984) Modelling with integer variables. Korte B, Ritter K, eds. Mathematical Programming at Oberwolfach II, Mathematical Programming Studies, vol. 22 (Springer-Verlag, Berlin), 167-184.Crossref, Google Scholar · Zbl 0554.90081 · doi:10.1007/BFb0121015
[10] [10] Lovász L (1989) Geometry of numbers and integer programming. Mathematical Programming, vol. 6 (SCIPRESS, Tokyo), 177-201.Google Scholar · Zbl 0683.90054
[11] [11] Lubin M, Zadik I, Vielma JP (2017) Mixed-integer convex representability. Eisenbrand F, Koenemann J, eds. Internat. Conf. Integer Programming Combinatorial Optim. IPCO 2017, Lecture Notes in Computer Science, vol. 10328 (Springer, Cham, Switzerland), 392-404.Crossref, Google Scholar · Zbl 1418.90179 · doi:10.1007/978-3-319-59250-3_32
[12] [12] Lubin M, Zadik I, Vielma JP (2017) Regularity in mixed-integer convex representability. Working paper, Google, New York.Google Scholar · Zbl 1418.90179
[13] [13] Martin RK (1999) Large Scale Linear and Integer Optimization: A Unified Approach (Springer, New York).Crossref, Google Scholar · Zbl 1053.90001 · doi:10.1007/978-1-4615-4975-8
[14] [14] Ryan J (1986) Integral monoid duality models. Unpublished doctoral thesis, Cornell University, Ithaca, NY.Google Scholar
[15] [15] Ryan J (1991) Decomposing finitely generated integral monoids by elimination. Linear Algebra Appl. 153:209-217.Crossref, Google Scholar · Zbl 0743.90080 · doi:10.1016/0024-3795(91)90220-Q
[16] [16] Schrijver A (1986) Theory of Linear and Integer Programming (Wiley, Chichester, UK).Google Scholar · Zbl 0665.90063
[17] [17] Vielma JP (2015) Mixed integer linear programming formulation techniques. SIAM Rev. 57(1):3-57.Crossref, Google Scholar · Zbl 1338.90277 · doi:10.1137/130915303
[18] [18] Williams HP (1976) Fourier-Motzkin elimination extension to integer programming problems. J. Combin. Theory A 21(1):118-123.Crossref, Google Scholar · Zbl 0326.90047 · doi:10.1016/0097-3165(76)90055-8
[19] [19] Williams HP (1986) Fourier’s method of linear programming and its dual. Amer. Math. Monthly 93(9):681-695.Crossref, Google Scholar · Zbl 0618.90065 · doi:10.1080/00029890.1986.11971923
[20] [20] Williams HP (1992) The elimination of integer variables. J. Oper. Res. Soc. 43(5):387-393.Crossref, Google Scholar · Zbl 0764.90065 · doi:10.1057/jors.1992.65
[21] [21] Williams HP, Hooker JN (2016) Integer programming as projection. Discrete Optim. 22:291-311.Crossref, Google Scholar · Zbl 1387.90146 · doi:10.1016/j.disopt.2016.08.004
[22] [22] Wolsey LA (1981) Integer programming duality: Price functions and sensitivity analysis. Math. Programming 20(1):173-195.Crossref, Google Scholar · Zbl 0458.90047 · doi:10.1007/BF01589344
[23] [23] Wolsey LA (1981) The b-hull of an integer program. Discrete Appl. Math. 3(3):193-201.Crossref, · Zbl 0457.90055 · doi:10.1016/0166-218X(81)90016-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.