Recovering Dantzig–Wolfe Bounds by Cutting Planes

References

• Andersen K, Pochet Y (2010) Coefficient strengthening: A tool for reformulating mixed-integer programs. Math. Programming 122(1):121–154.Crossref, Google Scholar
• Anjos MF, Lodi A, Tanneau M (2018) A decentralized framework for the optimal coordination of distributed energy resources. IEEE Trans. Power Systems 34(1):349–359.Crossref, Google Scholar
• Avella P, Boccia M, Vasilyev I (2010) A computational study of exact knapsack separation for the generalized assignment problem. Comput. Optim. Appl. 45:543–555.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Bartlett M, Frisch AM, Hamadi Y, Miguel I, Tarim SA, Unsworth C (2005) The temporal knapsack problem and its solution. Barták R, Milano M, eds. Internat. Conf. Integration Artificial Intelligence (AI) Oper. Res. (OR) Techniques Constraint Programming (Springer, Berlin, Heidelberg), 34–48.Google Scholar
• Berthold T, Francobaldi M, Hendel G (2022) Learning to use local cuts. Preprint, submitted June 23, https://arxiv.org/abs/2206.11618.Google Scholar
• Bodur M, Ahmed S, Boland N, Nemhauser GL (2022) Decomposition of loosely coupled integer programs: A multiobjective perspective. Math. Programming 196:427–477.Crossref, Google Scholar
• Bonami P, Lodi A, Zarpellon G (2022) A classifier to decide on the linearization of mixed-integer quadratic problems in CPLEX. Oper. Res. 70(6):3303–3320.Link, Google Scholar
• Boyd EA (1994) Fenchel cutting planes for integer programs. Oper. Res. 42(1):53–64.Link, Google Scholar
• Caprara A, Furini F, Malaguti E (2013) Uncommon Dantzig–Wolfe reformulation for the temporal knapsack problem. INFORMS J. Comput. 25(3):560–571.Link, Google Scholar
• Ceselli A, Righini G (2005) A branch-and-price algorithm for the capacitated p-median problem. Networks 45(3):125–142.Crossref, Google Scholar
• Chvátal V, Cook W, Espinoza D (2013) Local cuts for mixed-integer programming. Math. Programming Comput. 5(2):171–200.Crossref, Google Scholar
• Cochran JJ, Cox LA Jr, Keskinocak P, Kharoufeh JP, Smith JC, Ahmed S (2011) Two-stage stochastic integer programming: A brief introduction. Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (Wiley, Hoboken, NJ), 1–10.Crossref, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming, vol. 271 (Springer, Berlin).Crossref, Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, Google Scholar
• Espinoza D, Fukasawa R, Goycoolea M (2010) Lifting, tilting and fractional programming revisited. Oper. Res. Lett. 38(6):559–563.Crossref, Google Scholar
• Fisher ML (1981) The Lagrangian relaxation method for solving integer programming problems. Management Sci. 27(1):1–18.Link, Google Scholar
• Galati MV, Ralphs TK, Wang J (2012) Computational experience with generic decomposition using the DIP framework, https://coral.ise.lehigh.edu/~ted/files/papers/RAMP12.pdf.Google Scholar
• Gamrath G, Lübbecke ME (2010) Experiments with a generic Dantzig–Wolfe decomposition for integer programs. Festa P, ed. Internat. Sympos. Experiment. Algorithms (Springer, Berlin, Heidelberg), 239–252.Google Scholar
• Gamrath G, Berthold T, Salvagnin D (2020) An exploratory computational analysis of dual degeneracy in mixed-integer programming. EURO J. Comput. Optim. 8(3–4):241–261.Crossref, Google Scholar
• Goldman AJ, Tucker AW (1956) Theory of linear programming. Linear Inequalities and Related Systems (Princeton University Press, Princeton, NJ), 53–98.Google Scholar
• Jünger M, Thienel S (2000) The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization. Software Practice Experience 30(11):1325–1352.Crossref, Google Scholar
• Kataoka S, Yamada T (2014) Upper and lower bounding procedures for the multiple knapsack assignment problem. Eur. J. Oper. Res. 237(2):440–447.Crossref, Google Scholar
• Kelley JE Jr (1960) The cutting-plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8(4):703–712.Crossref, Google Scholar
• Lemaréchal C, Nemirovskii A, Nesterov Y (1995) New variants of bundle methods. Math. Programming 69(1):111–147.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 (Springer, Berlin), 619–645.Crossref, Google Scholar
• Lodi A, Tramontani A (2014) Performance variability in mixed-integer programming. INFORMS TutORials Oper. Res. Theory Driven Influential Appl. September:1–12.Google Scholar
• Lübbecke ME, Zimmermann UT (2003) Engine routing and scheduling at industrial in-plant railroads. Transportation Sci. 37(2):183–197.Link, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183(1):483–523.Crossref, Google Scholar
• Puchinger J, Stuckey PJ, Wallace M, Brand S (2008) From high-level model to branch-and-price solution in G12. Perron L, Trick MA, eds. Internat. Conf. Integration Artificial Intelligence (AI) Oper. Res. (OR) Techniques Constraint Programming (Springer, Berlin, Heidelberg), 218–232.Google Scholar
• Ralphs TK, Galati MV (2005) Decomposition in integer linear programming. Karlof JK, ed. Integer Programming (CRC Press, Boca Raton, FL), 73–126.Crossref, Google Scholar
• Ralphs TK, Kopman L, Pulleyblank WR, Trotter LE (2003) On the capacitated vehicle routing problem. Math. Programming 94:343–359.Crossref, Google Scholar
• Rios J, Ross K (2010) Massively parallel Dantzig–Wolfe decomposition applied to traffic flow scheduling. J. Aerospace Comput. Inform. Comm. 7(1):32–45.Crossref, Google Scholar
• Sadykov R, Vanderbeck F (2021) BaPCod—A generic branch-and-price code. PhD thesis, Inria Bordeaux Sud-Ouest, Talence, France.Google Scholar
• Savelsbergh M (1997) A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45(6):831–841.Link, Google Scholar
• Shapiro JF (1971) Generalized Lagrange multipliers in integer programming. Oper. Res. 19(1):68–76.Link, Google Scholar
• Shapiro A, Dentcheva D, Ruszczynski A (2021) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Crossref, Google Scholar
• Singh KJ, Philpott AB, Wood RK (2009) Dantzig–Wolfe decomposition for solving multistage stochastic capacity-planning problems. Oper. Res. 57(5):1271–1286.Link, Google Scholar
• Vanderbeck F (2000) On Dantzig–Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48(1):111–128.Link, Google Scholar
• Wolsey LA, Nemhauser GL (1999) Integer and Combinatorial Optimization, vol. 55 (John Wiley & Sons, Hoboken, NJ).Google Scholar