Cut-generating functions and \(S\)-free sets. (English) Zbl 1317.52017
Summary: We consider the separation problem for sets \(X\) that are pre-images of a given set \(S\) by a linear mapping. Classical examples occur in integer programming, as well as in other optimization problems such as complementarity. One would like to generate valid inequalities that cut off some point not lying in \(X\), without reference to the linear mapping. To this aim, we introduce a concept: cut-generating functions (CGF) and we develop a formal theory for them, largely based on convex analysis. They are intimately related to \(S\)-free sets and we study this relation, disclosing several definitions for minimal CGF’s and maximal \(S\)-free sets. Our work unifies and puts into perspective a number of existing works on \(S\)-free sets; in particular, we show how CGF’s recover the celebrated Gomory cuts.
MSC:
| 52A41 | Convex functions and convex programs in convex geometry |
| 90C11 | Mixed integer programming |
| 52A40 | Inequalities and extremum problems involving convexity in convex geometry |
References:
| [1] | Andersen K, Louveaux Q, Weismantel R, Wolsey L (2007) Cutting planes from two rows of a simplex tableau. Fischetti M, Williamson D, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 4513 (Springer, Berlin), 1-15. · Zbl 1136.90517 |
| [2] | Averkov G (2013) On maximal S-free sets and the Helly number of the family of S-convex sets. SIAM J. Discrete Math. 27:1610-1624. CrossRef · Zbl 1282.90109 |
| [3] | Balas E (1979) Disjunctive programming. Ann. Discrete Math. 5:3-51. CrossRef · Zbl 0409.90061 |
| [4] | Basu A, Cornuéjols G, Zambelli G (2011) Convex sets and minimal sublinear functions. J. Convex Anal. 18(2):427-432. · Zbl 1220.26009 |
| [5] | 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. Abstract · Zbl 1218.90130 |
| [6] | Basu A, Conforti M, Cornuéjols G, Zambelli G (2010) Minimal inequalities for an infinite relaxation of integer programs. SIAM J. Discrete Math. 24(1):158-168. CrossRef · Zbl 1211.90139 |
| [7] | Bixby R, Rothberg E (2007) Progress in computational mixed integer programming–A look back from the other side of the tipping point. Ann. Oper. Res. 149(1):37-41. CrossRef · Zbl 1213.90011 |
| [8] | Borozan V, Cornuéjols G (2009) Minimal valid inequalities for integer constraints. Math. Oper. Res. 34(3):538-546. Abstract · Zbl 1218.90131 |
| [9] | Caprari E, Zaffaroni A (2010) Conically equivalent convex sets and applications. Pacific J. Optim. 6:281-303. · Zbl 1196.52002 |
| [10] | Cornuéjols G, Lemaréchal C (2005) A convex-analysis perspective on disjunctive cuts. Math. Programming 106(3):567-586. CrossRef · Zbl 1149.90175 |
| [11] | Cornuéjols G, Yildiz S, Wolsey LA (2014) Sufficiency of cut-generating functions. Math. Programming, Ser. A, ePub ahead of print April 19, http://link.springer.com/article/10.1007/s10107-014-0780-2. |
| [12] | Dey SS, Wolsey LA (2010) Constrained infinite group relaxations of MIPs. SIAM J. Optim. 20(6):2890-2912. CrossRef · Zbl 1211.90142 |
| [13] | Gomory RE (1963) An algorithm for integer solutions to linear programs. Graves RL, Wolfe P, eds. Recent Advances in Mathematical Programming (McGraw-Hill, New York), 269-302. |
| [14] | Gomory RE (1969) Some polyhedra related to combinatorial problems. Linear Alg. Appl. 2(4):451-558. CrossRef · Zbl 0184.23103 |
| [15] | Gomory RE, Johnson EL (1972) Some continuous functions related to corner polyhedra i. Math. Programming 3:23-85. CrossRef · Zbl 0246.90029 |
| [16] | Hiriart-Urruty J-B, Lemaréchal C (1993) Convex Analysis and Minimization Algorithms (Springer, Berlin). · Zbl 0795.49001 |
| [17] | Hiriart-Urruty J-B, Lemaréchal C (2001) Fundamentals of Convex Analysis (Springer, Berlin). CrossRef |
| [18] | Johnson EL (1981) Characterization of facets for multiple right-hand side choice linear programs. Math. Programming Study 14:112-142. CrossRef · Zbl 0449.90070 |
| [19] | Júdice JJ, Sherali H, Ribeiro IM, Faustino AM (2006) A complementarity-based partioning and disjujnctive cut algorithm for mathematical programming problems with equilibrium constraints. J. Global Optim. 136:89-114. CrossRef |
| [20] | Kilinç-Karzan F (2013) On minimal valid inequalities for mixed integer conic programs. Working Paper 2013-E20, GSIA, Carnegie Mellon University, Pittsburgh. |
| [21] | Lovász L (1989) Geometry of numbers and integer programming. Iri M, Tanabe K, eds. Mathematical Programming: Recent Developements and Applications (Kluwer Academic Publishers, Amsterdam), 177-210. |
| [22] | Morán R, Dey SS (2011) On maximal S-free convex sets. SIAM J. Discrete Math. 25:379-393. CrossRef · Zbl 1226.90045 |
| [23] | Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ). |
| [24] | Zaffaroni A (2013) Convex radiant costarshaped sets and the least sublinear gauge. J. Convex Anal. 20(2):307-328. · Zbl 1275.52002 |
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.
