[en] We develop a method for computing facet-defining valid inequalities for any mixed-integer set PJ. Our practical implementation does not return only facet- defining inequalities, but it is able to find a separating cut whenever one exists. The separator is not comparable in speed with the specific cutting-plane generators used in branch-and-cut solvers, but it is general-purpose. We can thus use it to compute cuts derived from any reasonably small relaxation PJ of a general mixed- integer problem, even when there exists no specific implementation for computing cuts with PJ. Exploiting this, we evaluate, from a computational perspective, the usefulness of cuts derived from several types of multi-row relaxations. In particular, we present results with four different strengthenings of the two-row intersection cut model, and multi-row models with up to fifteen rows. We conclude that only fully-strengthened two-row cuts seem to offer a significant advantage over two-row intersection cuts. Our results also indicate that the improvement obtained by going from models with very few rows to models with up to fifteen rows may not be worth the increased computing cost.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
Louveaux, Quentin ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète
Poirrier, Laurent; University of Waterloo > Department of Optimization and Combinatorics
Salvagnin, Domenico; University of Padova > Department of Information Engineering
Andersen, K., Louveaux, Q., Weismantel, R.: Mixed-integer sets from two rows of two adjacent simplex bases. Math. Program. 124, 455–480 (2010)
Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.: Inequalities from two rows of a simplex tableau. In: Fischetti, M., Williamson, D. (eds.) Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 4513, pp. 1–15. Springer, Berlin (2007)
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: TSP cuts which do not conform to the template paradigm. Lect. Notes Comput. Sci. 2241, 261–303 (2001)
Balas, E.: Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 1(19), 19–39 (1971)
Balas, E., Perregaard, M.: Lift-and-project for mixed 0–1 programming: recent progress. Discrete Appl. Math. 123(1–3), 129–154 (2002)
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. Program. 94(2–3), 221–245 (2003)
Basu, A., Bonami, P., Cornuéjols, G., Margot, F.: Experiments with two-row cuts from degenerate tableaux. INFORMS J. Comput. 23, 578–590 (2011)
Basu, A., Conforti, M., Cornuéjols, G., Giacomo, Z.: Minimal inequalities for an infinite relaxation of integer programs. SIAM J. Discrete Math. 24, 158–168 (2010)
Basu, A., Cornuéjols, G., Molinaro, M.: A probabilistic analysis of the strength of the split and triangle closures. In: Günlük, O., Woeginger, G.J. (eds.) Integer Programming and Combinatoral Optimization. Lecture Notes in Computer Science, vol. 6655, pp. 27–38. Springer, Berlin (2011)
Boyd, A.E.: Generating Fenchel cutting planes for knapsack polyhedra. SIAM J. Optim. 3(4), 734–750 (1993)
Chvátal, V., Cook, W., Espinoza, D.: Local cuts for mixed-integer programming. Math. Program. Comput. 5(2), 171–200 (2013)
Conforti, M., Cornuéjols, G., Zambelli, G.: A geometric perspective on lifting. Oper. Res. 59, 569–577 (2011)
Cornuéjols, G., Margot, F.: On the facets of mixed integer programs with two integer variables and two constraints. Math. Program. 120(2), 429–456 (2009)
Dash, S., Dey, S.S., Günlük, O.: Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra. Math. Program. 135(1–2), 221–254 (2012)
Dash, S., Goycoolea, M.: A heuristic to generate rank-1 GMI cuts. Math. Program. Comput. 2(3–4), 231–257 (2010)
Dash, S., Günlük, O., Vielma, J.P.: Computational experiments with cross and crooked cross cuts. IBM Technical Report (2011)
Dey, S.S., Wolsey, L.A.: Two row mixed-integer cuts via lifting. Math. Program. 124, 143–174 (2010)
Dey, S.S., Lodi, A., Tramontani, A., Wolsey, L.A.: Experiments with two row tableau cuts. In: Eisenbrand, F., Bruce Shepherd, F. (eds.) Integer Programming and Combinatorial Optimization. Proceedings of the 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9–11, 2010. Lecture Notes in Computer Science, vol. 6080, pp. 424–437. Springer, Berlin (2010)
Dey, S.S., Lodi, A., Tramontani, A., Wolsey, L.A.: On the practical strength of two-row tableau cuts. INFORMS J. Comput. 26(2), 222–237 (2014)
Dey, S.S., Louveaux, Q.: Split rank of triangle and quadrilateral inequalities. Math. Oper. Res. 36(3), 432–461 (2011)
Dey, S.S., Richard, J.-P.P.: Linear-programming-based lifting and its application to primal cutting-plane algorithms. INFORMS J. Comput. 21(1), 137–150 (2010)
Dey, S.S., Wolsey, L.A.: Lifting integer variables in minimal inequalities corresponding to lattice-free triangles. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) Integer Programming and Combinatorial Optimization. Proccedings of the13th International Conference, IPCO 2008, Bertinoro, Italy, May 26–28, 2008. Lecture Notes in Computer Science, vol. 5035, pp. 463–475. Springer, Berlin (2008)
Dey, S.S., Wolsey, L.A.: Constrained infinite group relaxations of MIPs. CORE Discussion Papers 2009033, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) (2009)
Espinoza, D.G.: Computing with multi-row Gomory cuts. Oper. Res. Lett. 38(2), 115–120 (2010)
Fischetti, M., Salvagnin, D.: A relax-and-cut framework for gomory’s mixed-integer cuts. Math. Program. Comput. 3, 79–102 (2011)
Fischetti, M., Salvagnin, D.: Approximating the split closure. INFORMS J. Comput. 25(4), 808–819 (2013)
Fukasawa, R., Günlük, O.: Strengthening lattice-free cuts using non-negativity. Discrete Optim. 8(2), 229–245 (2011)
Fukasawa, R., Goycoolea, M.: On the exact separation of mixed integer knapsack cuts. Math. Program. 128, 19–41 (2011)
Gomory, R.E.: On the relation between integer and noninteger solutions to linear programs. Proc. Natl. Acad. Sci. 53, 260–265 (1965)
Gomory, R.E.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2(4), 451–558 (1969)
Gomory, R.E., Johnson, E.L.: Some continuous functions related to corner polyhedra, part I. Math. Program. 3, 23–85 (1972)
Louveaux, Q., Poirrier, L.: An algorithm for the separation of two-row cuts. Math. Program. 143(1–2), 111–146 (2014)
Margot, F.: MIPLIB3 C V2. http://wpweb2.tepper.cmu.edu/fmargot/ (2009)
Nemhauser, G.L., Wolsey, L.A.: A recursive procedure to generate all cuts for 0–1 mixed integer programs. Math. Program. 46, 379–390 (1990)
Perregaard, M., Balas, E.: Generating cuts from multiple-term disjunctions. In: Aardal, K., Gerards, B. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 2081, pp. 348–360. Springer, Berlin (2001)
Poirrier, L.: Multi-row approaches to cutting plane generation. PhD thesis, University of Liège (2012)
Richard, J.-P.P., de Farias Jr, I.R., Nemhauser, G.L.: Lifted inequalities for 0–1 mixed integer programming: basic theory and algorithms. Math. Program. 98(1–3), 89–113 (2003)
Schrijver, A.: Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1998)
