Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs

References

• 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.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• Bixby RE, Fenelon M, Gu Z, Rothberg E, R Wunderling R (2004) Mixed-Integer Programming: A Progress Report, Chap. 18 (SIAM, Philadelphia), 309–326.Google Scholar
• 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.Link, Google Scholar
• 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.Google Scholar
• Borndörfer R, Ferreira CE, Martin A (1998) Decomposing matrices into blocks. SIAM J. Optim. 9(1):236–269.Crossref, Google Scholar
• Brooks RL (1941) On colouring the nodes of a network. Proc. Cambridge Philosophical Soc. 37(2):194–197.Crossref, Google Scholar
• Carøe CC, Schultz R (1999) Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24(1–2):37–45.Crossref, Google Scholar
• Colbourn CJ, Dinitz JH (2006) Handbook of Combinatorial Designs, 2nd ed. (Chapman & Hall/CRC, Boca Raton, FL).Crossref, Google Scholar
• Crowder H, Johnson EL, Padberg MW (1983) Solving large-scale zero-one linear programming problem. Oper. Res. 31(5):803–834.Link, Google Scholar
• Dey SS, Molinaro M, Wang Q (2015) Approximating polyhedra with sparse inequalities. Math. Programming 154:329–352.Crossref, Google Scholar
• 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.Link, Google Scholar
• 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.Crossref, Google Scholar
• Fulkerson DR, Gross O (1965) Incidence matrices and interval graphs. Pacific J. Math. 15:835–855.Crossref, Google Scholar
• King AD, Lu L, Peng X (2012) A fractional analogue of Brooks’ theorem. SIAM J. Discrete Math. 26(2):452–471.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• Lodi A (2010) Mixed integer programming computation 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), 619–645.Crossref, Google Scholar
• Lovász L (1975) On the ratio of the optimal integral and fractional covers. Discrete Math. 13(4):383–390.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• Molloy M, Reed B (2002) Graph Colouring and the Probabilistic Method (Springer, Berlin).Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• 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.Google Scholar
• 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.Crossref, Google Scholar
• Zhang M (2014) Küçükyavuz S Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs. SIAM J. Optim. 24(4):1933–1951.Crossref, Google Scholar