[en] We consider the question of finding deep cuts from a model with two rows of the type PI = {(x,s) ∈ Z2 ×Rn+ : x = f +Rs}. To do that, we show how to reduce the complexity of setting up the polar of conv(PI ) from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore, we present an algorithm that avoids computing all integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice.
Disciplines :
Computer science
Author, co-author :
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 ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)
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.: Cutting planes from two rows of a simplex tableau (extended version), (2006). Working paper available on http://orbi.ulg.ac.be/handle/2268/82794
Andersen, K.; Louveaux, Q.; Weismantel, R.; Wolsey, L.: Inequalities from two rows of a simplex tableau. In: Matteo, F.; David, W. (eds.) Integer Programming and Combinatorial Optimization, vol. 4513 of Lecture Notes in Computer Science, pp. 1-15. Springer, Berlin (2007)
Andersen, K.; Wagner, C.; Weismantel, R.: On an analysis of the strength of mixed-integer cutting planes from multiple simplex tableau rows. SIAM J. Optimiz. 20(2), 967-982 (2009)
Barvinok, A.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19(4), 769-779 (1994)
Barvinok, A.: Integer Points in Polyhedra Zurich Lectures in Advanced Mathematics. European Mathematical Society, Madralin (2008)
Basu, A.; Conforti, M.; Cornuéjols, G.; Zambelli, G.: Minimal inequalities for an infinite relaxation of integer programs. SIAM J. Discret. Math. 24, 158-168 (2010)
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.; Bonami, P.; Cornuéjols, G.; Margot, F.: On the relative strength of split, triangle and quadrilateral cuts. In: SODA, pp. 1220-1229. SIAM, Philadelphia (2009)
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)
Dey, S.S.; Lodi, A.; Tramontani, A.; Wolsey, L.A.: Experiments with two row tableau cuts. In: Eisenbrand, F.; Shepherd, F.B. (eds.) Integer Programming and Combinatorial Optimization, 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings, Vol. 6080 of Lecture Notes in Computer Science, pp. 424-437. Springer, Berlin (2010)
Dey, S.S.; Louveaux, Q.: Split rank of triangle and quadrilateral inequalities. Math. Oper. Res. 36(3), 432-461 (2011)
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, 13th International Conference, IPCO 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings, vol. 5035 of Lecture Notes in Computer Science, 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), (May 2009)
Espinoza, D.G.: Computing with multi-row Gomory cuts. Oper. Res. Lett. 38(2), 115-120 (2010)
