×

zbMATH — the first resource for mathematics

On optimizing over lift-and-project closures. (English) Zbl 1275.90042
Summary: The strengthened lift-and-project closure of a mixed integer linear program is the polyhedron obtained by intersecting all strengthened lift-and-project cuts obtained from its initial formulation, or equivalently all mixed integer Gomory cuts read from all tableaux corresponding to feasible and infeasible bases of the LP relaxation. In this paper, we present an algorithm for approximately optimizing over the strengthened lift-and-project closure. The originality of our method is that it relies on a cut generation linear programming problem which is obtained from the original LP relaxation by only modifying the bounds on the variables and constraints. This separation LP can also be seen as dual to the cut generation LP used in disjunctive programming procedures with a particular normalization. We study properties of this separation LP, and discuss how to use it to approximately optimize over the strengthened lift-and-project closure. Finally, we present computational experiments and comparisons with recent related works.

MSC:
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen K., Cornuéjols G., Li Y.: Reduce-and-split cuts: improving the performance of mixed integer Gomory cuts. Manag. Sci. 50(11), 1720–1732 (2005) · Zbl 1232.90310 · doi:10.1287/mnsc.1050.0382
[2] Andersen K., Cornuéjols G., Li Y.: Split closure and intersection cuts. Math. Progr. 102, 457–493 (2005) · Zbl 1066.90070 · doi:10.1007/s10107-004-0558-z
[3] Balas E.: Intersection cuts–a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971) · Zbl 0219.90035 · doi:10.1287/opre.19.1.19
[4] Balas E.: Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebraic Discret. Methods 6(3), 466–486 (1985) · Zbl 0592.90070 · doi:10.1137/0606047
[5] Balas, E.: Disjunctive programming: Properties of the convex hull of feasible points. Discret. Appl. Math. 89, 3–44 (1998) (originally MSRR # 348, Carnegie Mellon University, July 1974) · Zbl 0921.90118
[6] Balas E., Bonami P.: Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants. Math. Progr. Comput. 1, 165–199 (2009) · Zbl 1180.90206 · doi:10.1007/s12532-009-0006-4
[7] Balas E., Ceria S., Cornuéjols G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Progr. 58, 295–324 (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273
[8] Balas E., Ceria S., Cornuéjols G.: Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Manag. Sci. 42, 1229–1246 (1996) · Zbl 0880.90105 · doi:10.1287/mnsc.42.9.1229
[9] Balas E., Jeroslow R.G.: Strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4(4), 224–234 (1980) · Zbl 0439.90064 · doi:10.1016/0377-2217(80)90106-X
[10] Balas E., Perregaard M.: Lift and project for mixed 0-1 programming: recent progress. Discret. Appl. Math. 123, 129–154 (2002) · Zbl 1076.90031 · doi:10.1016/S0166-218X(01)00340-7
[11] Balas E., Perregaard M.: A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0-1 programming. Math. Progr. 94, 221–245 (2003) · Zbl 1030.90068 · doi:10.1007/s10107-002-0317-y
[12] Balas E., Saxena A.: Optimizing over the split closure. Math. Progr. 113, 219–240 (2008) · Zbl 1135.90030 · doi:10.1007/s10107-006-0049-5
[13] Balas E., Zemel E.: Facets of the knapsack polytope from minimal covers. SIAM J. Appl. Math. 34, 119–148 (1978) · Zbl 0385.90083 · doi:10.1137/0134010
[14] Bixby, R., Ceria, S., McZeal, C., Savelsbergh, M.: Miplib 3.0. http://www.caam.rice.edu/\(\sim\)bixby/miplib/miplib.html (1998)
[15] Bixby, R., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: The Sharpest cut, chapter mixed-integer programming: a progress report, pp. 309–326. MPS-SIAM Series on Optimization. SIAM (2004) · Zbl 1152.90542
[16] Bonami, P., Balas, E.: Cgllandp. https://projects.coin-or.org/cgl/wiki/cgllandp . July (2006)
[17] Bonami P., Cornuéjols G., Dash S., Fischetti M., Lodi A.: Projected Chvátal–Gomory cuts for mixed integer linear programs. Math. Progr. Series A 113(2), 241–257 (2008) · Zbl 1135.90031 · doi:10.1007/s10107-006-0051-y
[18] Bonami P., Minoux M.: Using rank-1 lift-and-project closures to generate cuts for 0–1 MIPs, a computational investigation. Discret. Optim. 2(4), 288–307 (2005) · Zbl 1172.90450 · doi:10.1016/j.disopt.2005.08.006
[19] Caprara A., Letchford A.N.: On the separation of split cuts and related inequalities. Math. Progr. 94(2–3), 279–294 (2003) · Zbl 1030.90095 · doi:10.1007/s10107-002-0320-3
[20] Chvátal V.: Edmonds polytopes and a hierarchy of combinatorial optimization. Discret. Math. 4, 305–337 (1973) · Zbl 0253.05131 · doi:10.1016/0012-365X(73)90167-2
[21] Cook W., Kannan R., Schrijver A.: Chvátal closures for mixed integer programming problems. Math. Progr. 47, 155–174 (1990) · Zbl 0711.90057 · doi:10.1007/BF01580858
[22] Cornuéjols G., Li Y.: Elementary closures for integer programs. Oper. Res. Lett. 28, 1–8 (2001) · Zbl 1108.90326 · doi:10.1016/S0167-6377(00)00067-5
[23] Cornuéjols, G., Nannicini, G. Practical strategies for generating rank-1 split cuts in mixed-integer linear programming. Math. Progr. Comput. pp. 1–38. doi: 10.1007/s12532-011-0028-6 · Zbl 1276.90040
[24] Dash S., Goycoolea M.: A heuristic to generate rank-1 gmi cuts. Math. Progr. Comput. 2, 231–257 (2010) · Zbl 1208.90120 · doi:10.1007/s12532-010-0018-0
[25] Dash S., Günlük O., Lodi A.: MIR closures of polyhedral sets. Math. Progr. 121(1), 33–60 (2010) · Zbl 1184.90107 · doi:10.1007/s10107-008-0225-x
[26] Eisenbrand, F.: On the membership problem for the elementary closure of a polyhedron. Combinatorica 19(2), (1999) · Zbl 0947.90071
[27] Fischetti M., Lodi A.: Optimizing over the first Chvátal closure. Math. Progr. 110, 3–20 (2007). doi: 10.1007/s10107-006-0054-8 · Zbl 1192.90125 · doi:10.1007/s10107-006-0054-8
[28] Fischetti M., Lodi A., Tramontani A.: On the separation of disjunctive cuts. Math. Progr. 128, 205–230 (2011) · Zbl 1218.90125 · doi:10.1007/s10107-009-0300-y
[29] Fischetti, M., Salvagnin, D.: An in-out approach to disjunctive optimization. In: Lodi, A., Milano, M., Toth, P., (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Lecture Notes in Computer Science, vol. 6140, pp. 136–140. Springer, Berlin (2010) · Zbl 1285.90018
[30] Fischetti M., Salvagnin D.: A relax-and-cut framework for gomory’s mixed-integer cuts. Math. Progr. Comput. 3, 79–102 (2011) · Zbl 1257.90057 · doi:10.1007/s12532-011-0024-x
[31] Forrest, J.: CLP. http://www.coin-or.org/ (2004)
[32] Gomory R.: An algorithm for integer solution solutions to linear programming. In: Graves, R.L., Wolfe, P. (eds) Recent Advances in Mathematical Programming, pp. 269–302. McGraw-Hill, New York (1963) · Zbl 0235.90038
[33] Gomory, R.E.: Solving linear programming problems in integers. In: Bellman R., Hall, M. (eds.) Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics, vol. 10, pp. 211–216. Providence (1960) · Zbl 0096.14505
[34] Kelley J.E.: The cutting plane method for solving convex programs. J. SIAM 8(4), 703–712 (1960) · Zbl 0098.12104
[35] Lougee-Heimer, R.: The common optimization interface for operations research. IBM J. Res. Dev. 47, 57–66 (2003). http://www.coin-or.org
[36] Martin, A., Achterberg, T., Koch, T.: MIPLIB 2003. http://miplib.zib.de (2003)
[37] Nemhauser G., Wolsey L.: A recursive procedure to generate all cuts for 0-1 mixed integer programs. Math. Progr. 46, 379–390 (1990) · Zbl 0735.90049 · doi:10.1007/BF01585752
[38] Padberg M., Roy T., Wolsey L.: Valid linear inequalities for fixed charge problems. Oper. Res. 33, 842–861 (1985) · Zbl 0579.90072 · doi:10.1287/opre.33.4.842
[39] Roy T.V., Wolsey L.: Solving mixed integer programming problems using automatic reformulation. Oper. Res. 35, 45–57 (1987) · Zbl 0614.90082 · doi:10.1287/opre.35.1.45
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.