×

Nonunique lifting of integer variables in minimal inequalities. (English) Zbl 1411.90220

Summary: We explore the lifting question in the context of cut-generating functions. Most of the prior literature on this question focuses on cut-generating functions that have the unique lifting property. We develop a general theory for understanding the lifting question for cut-generating functions that do not necessarily have the unique lifting property.

MSC:

90C10 Integer programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] G. Averkov and A. Basu, Lifting properties of maximal lattice-free polyhedra, Math. Program., 154 (2015), pp. 81-111. · Zbl 1328.90084
[2] A. Basu, M. Campêlo, M. Conforti, G. Cornuéjols, and G. Zambelli, Unique lifting of integer variables in minimal inequalities, Math. Program., 141 (2013), pp. 561-576. · Zbl 1354.90077
[3] A. Basu, M. Conforti, G. Cornuéjols, and G. Zambelli, Minimal inequalities for an infinite relaxation of integer programs, SIAM J. Discrete Math., 24 (2010), pp. 158-168. · Zbl 1211.90139
[4] A. Basu, M. Conforti, and M. Di Summa, A geometric approach to cut-generating functions, Math. Program., 151 (2015), pp. 153-189. · Zbl 1328.90085
[5] A. Basu, M. Conforti, M. D. Summa, and J. Paat, The structure of the infinite models in integer programming, in Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO), F. Eisenbrand and J. Koenemann, eds., Lecture Notes in Comput. Sci. 10328, Springer, Berlin, 2017. · Zbl 1418.90159
[6] A. Basu, G. Cornuéjols, and M. Köppe, Unique minimal liftings for simplicial polytopes, Math. Oper. Res., 37 (2012), pp. 346-355. · Zbl 1242.90116
[7] A. Basu, G. Cornuéjols, and G. Zambelli, Convex sets and minimal sublinear functions, J. Convex Anal., 18 (2011), pp. 427-432. · Zbl 1220.26009
[8] A. Basu, R. Hildebrand, and M. Köppe, Light on the infinite group relaxation I: Foundations and taxonomy, 4OR, 14 (2015), pp. 1-40. · Zbl 1353.90089
[9] A. Basu, R. Hildebrand, and M. Köppe, Light on the infinite group relaxation II: Sufficient conditions for extremality, sequences, and algorithms, 4OR, 14 (2015), pp. 1-25.
[10] A. Basu and J. Paat, Operations that preserve the covering property of the lifting region, SIAM J. Optim., 25 (2015), pp. 2313-2333. · Zbl 1327.90125
[11] L. E. J. Brouwer, Beweis der invarianz desn-dimensionalen gebiets, Math. Ann., 71 (1911), pp. 305-313.
[12] M. Conforti, G. Cornuéjols, A. Daniilidis, C. Lemaréchal, and J. Malick, Cut-generating functions, in Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO), Springer, Berlin, 2013, pp. 123-132. · Zbl 1372.90071
[13] M. Conforti, G. Cornuéjols, A. Daniilidis, C. Lemaréchal, and J. Malick, Cut-generating functions and S-free sets, Math. Oper. Res., 40 (2014), pp. 276-391. · Zbl 1317.52017
[14] M. Conforti, G. Cornuéjols, and G. Zambelli, Corner polyhedra and intersection cuts, Surv. Oper. Res. Manag. Sci., 16 (2011), pp. 105-120.
[15] M. Conforti, G. Cornuéjols, and G. Zambelli, A geometric perspective on lifting, Oper. Res., 59 (2011), pp. 569-577. · Zbl 1257.90053
[16] M. Conforti, G. Cornuéjols, and G. Zambelli, Integer Programming, Vol. 271, Springer, Berlin, 2014.
[17] M. Conforti, M. Di Summa, and L. A. Wolsey, The mixing set with flows, SIAM J. Discrete Math., 21 (2007), pp. 396-407. · Zbl 1171.90477
[18] M. Conforti, B. Gerards, and G. Zambelli, Mixed-integer vertex covers on bipartite graphs, in Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, Springer, Berlin, 2007, pp. 324-336. · Zbl 1136.90488
[19] J. B. Conway, A Course in Functional Analysis, Vol. 96, Springer, Berlin, 2013.
[20] S. Dash and O. Günlük, On mixing inequalities: Rank, closure, and cutting-plane proofs, SIAM J. Optim., 20 (2009), pp. 1090-1109. · Zbl 1198.90300
[21] S. S. Dey, A note on the split rank of intersection cuts, Math. Program., 130 (2011), pp. 107-124. · Zbl 1230.90136
[22] S. S. Dey, J.-P. P. Richard, Y. Li, and L. A. Miller, On the extreme inequalities of infinite group problems, Math. Program., 121 (2009), pp. 145-170.
[23] S. S. Dey and L. A. Wolsey, Composite lifting of group inequalities and an application to two-row mixing inequalities, Discrete Optim., 7 (2010), pp. 256-268. · Zbl 1242.90128
[24] S. S. Dey and L. A. Wolsey, Two row mixed-integer cuts via lifting, Math. Program., 124 (2010), pp. 143-174. · Zbl 1247.90205
[25] A. Dold, Lectures on Algebraic Topology, Springer, Berlin, 1995. · Zbl 0872.55001
[26] J. Dugundji, Topology, Allyn and Bacon, Boston, 1966.
[27] O. Günlük and Y. Pochet, Mixing mixed-integer inequalities, Math. Program., 90 (2001), pp. 429-457. · Zbl 1041.90033
[28] J. Luedtke, S. Ahmed, and G. L. Nemhauser, An integer programming approach for linear programs with probabilistic constraints, Math. Program., 122 (2010), pp. 247-272. · Zbl 1184.90115
[29] D. A. Morán R and S. S. Dey, On maximal S-free convex sets, SIAM J. Discrete Math., 25 (2011), p. 379.
[30] J.-P. P. Richard and S. S. Dey, The group-theoretic approach in mixed integer programming, in 50 Years of Integer Programming 1958-2008, M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, eds., Springer Berlin, 2010, pp. 727-801.
[31] M. Van Vyve, The continuous mixing polyhedron, Math. Oper. Res., 30 (2005), pp. 441-452. · Zbl 1082.90075
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.