Analysis of sparse cutting planes for sparse MILPs with applications to stochastic MILPs. (English) Zbl 1432.90090
Summary: In this paper, we present an analysis of the strength of sparse cutting planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is nonnegative. Given an MILP instance of one of these three types, assume that we decide on the support of cutting planes to be used and the strongest inequalities on these supports are added to the linear programming relaxation. We present bounds on the ratio of optimal value of the LP relaxation after adding cuts and the optimal value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. These results also shed light on the strength of single-scenario cuts for two-stage stochastic MILPs.
References:
| [1] | Acer S, Kayaaslan E, Aykanat C (2013) A recursive bipartitioning algorithm for permuting sparse square matrices into block diagonal form with overlap. SIAM J. Scientific Comput. 35(1):C99-C121. · Zbl 1263.05059 · doi:10.1137/120861242 |
| [2] | Bergner M, Caprara A, Furini F, Lübbecke ME, Malaguti E, Traversi E (2011) Partial convexification of general MIPs by Dantzig-Wolfe reformulation. Günlük O, Woeginger GJ, eds., Proc. 15th Internat. Conf. Integer Programming Combinatoral Optimization, IPCO 2011, Lecture Notes in Computer Science, Vol. 6655 (Springer, Berlin), 39-51. · Zbl 1339.90242 · doi:10.1007/978-3-642-20807-2_4 |
| [3] | Bixby RE, Fenelon M, Gu Z, Rothberg E, R Wunderling R (2004) Mixed-Integer Programming: A Progress Report, Chap. 18 (SIAM, Philadelphia), 309-326. |
| [4] | Bodur M, Dash S, Gunluk O, Luedtke J (2017) Strengthened benders cuts for stochastic integer programs with continuous recourse. INFORMS J. Comput. 29(1:77-91. · Zbl 1364.90220 |
| [5] | Bodur M, del Pia A, Dey SS, Molinaro M, Pokutta S (2016) Aggregation-based cutting-planes for packing and covering integer programs. CoRR abs/1606.08951. |
| [6] | Borndörfer R, Ferreira CE, Martin A (1998) Decomposing matrices into blocks. SIAM J. Optim. 9(1):236-269. · Zbl 1032.90523 · doi:10.1137/S1052623497318682 |
| [7] | Brooks RL (1941) On colouring the nodes of a network. Proc. Cambridge Philosophical Soc. 37(2):194-197. · JFM 67.0733.02 · doi:10.1017/S030500410002168X |
| [8] | Carøe CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1-2):37-45. · Zbl 1063.90037 · doi:10.1016/S0167-6377(98)00050-9 |
| [9] | Colbourn CJ, Dinitz JH (2006) Handbook of Combinatorial Designs, 2nd ed. (Chapman & Hall/CRC, Boca Raton, FL). · doi:10.1201/9781420010541 |
| [10] | Crowder H, Johnson EL, Padberg MW (1983) Solving large-scale zero-one linear programming problem. Oper. Res. 31(5):803-834. · Zbl 0576.90065 |
| [11] | Dey SS, Molinaro M, Wang Q (2015) Approximating polyhedra with sparse inequalities. Math. Programming 154:329-352. · Zbl 1327.90134 · doi:10.1007/s10107-015-0925-y |
| [12] | Dey SS, Lodi A, Tramontani A, Wolsey LA (2014) On the practical strength of two-row tableau cuts. INFORMS J. Comput. 26(2):222-237. · Zbl 1356.90090 |
| [13] | Escoffier B, Gourvès L, Monnot J, Spanjaard O (2010) Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation. Eur. J. Oper. Res. 205(1):19-30. · Zbl 1187.90208 · doi:10.1016/j.ejor.2009.12.004 |
| [14] | Fulkerson DR, Gross O (1965) Incidence matrices and interval graphs. Pacific J. Math. 15:835-855. · Zbl 0132.21001 · doi:10.2140/pjm.1965.15.835 |
| [15] | King AD, Lu L, Peng X (2012) A fractional analogue of Brooks’ theorem. SIAM J. Discrete Math. 26(2):452-471. · Zbl 1248.05166 · doi:10.1137/110827879 |
| [16] | Kong N, Schaefer AJ (2006) A factor 1/2 approximation algorithm for two-stage stochastic matching problems. Eur. J. Oper. Res. 172(3):740-746. · Zbl 1111.90075 · doi:10.1016/j.ejor.2004.10.011 |
| [17] | Lodi A (2010) Mixed integer programming computationJünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958-2008—From the Early Years to the State-of-the-Art (Springer, Berlin), 619-645. · Zbl 1187.90206 · doi:10.1007/978-3-540-68279-0_16 |
| [18] | Lovász L (1975) On the ratio of the optimal integral and fractional covers. Discrete Math. 13(4):383-390. · Zbl 0323.05127 · doi:10.1016/0012-365X(75)90058-8 |
| [19] | Marchand H, Martin A, Weismantel R, Wolsey LA (2002) Cutting planes in integer and mixed integer programming. Discrete Appl. Math. 123(1-3):397-446. · Zbl 1130.90370 · doi:10.1016/S0166-218X(01)00348-1 |
| [20] | Molloy M, Reed B (2002) Graph Colouring and the Probabilistic Method (Springer, Berlin). · Zbl 0987.05002 · doi:10.1007/978-3-642-04016-0 |
| [21] | Richard JPP, Dey SS (2010) The group-theoretic approach in mixed integer programming. Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958-2008—From the Early Years to the State-of-the-Art (Springer, Berlin), 727-801. · Zbl 1187.90004 · doi:10.1007/978-3-540-68279-0_19 |
| [22] | Sen S, Higle J (2005) The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Math. Programming 104(1):1-20. · Zbl 1159.90464 · doi:10.1007/s10107-004-0566-z |
| [23] | Walter M (2012) Sparsity of lift-and-project cutting planes. Helber S, Breitner M, Rsch D, Schn C, Graf Von der Schulenburg JM, Sibbertsen P, Steinbach M, Weber S, Wolter A, eds., Oper. Res. Proc. 2012, Operations Research Proceedings (Springer International, Cham, Switzerland), 9-14. · Zbl 1305.90313 |
| [24] | Wang J, Ralphs TK (2013) Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization. Gomes CP, Sellmann M, eds., Proc. 10th Internat. Conf. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2013, Lecture Notes in Computer Science, Vol. 7874 (Springer, Berlin), 394-402. · Zbl 1382.90119 · doi:10.1007/978-3-642-38171-3_31 |
| [25] | Zhang M (2014) Küçükyavuz S Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. · Zbl 1311.90081 · doi:10.1137/13092678X |
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.
