DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods

References

• Achterberg T (2018) Exploiting degeneracy in MIP. Presentation, Aussois 22nd Combinatorial Optimization Workshop, CNRS Centre Paul Langevin, Aussois, France, http://www.iasi.cnr.it/aussois/web/uploads/2018/slides/achterbergt.pdf.Google Scholar
• Achterberg T, Berthold T, Koch T, Wolter K (2008) Constraint integer programming: A new approach to integrate CP and MIP. Perron L, Trick MA, eds. Integration AI OR Techniques Constraint Programming Combin. Optim. Problems 5th Internat. Conf. CPAIOR 2008 (Springer, Berlin), 6–20.Google Scholar
• Aloise D, Deshpande A, Hansen P, Popat P (2009) NP-hardness of Euclidean sum-of-squares clustering. Machine Learn. 75:245–248.Crossref, Google Scholar
• Amaldi E, Kann V (1995) The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoret. Comput. Sci. 147(1–2):181–210.Crossref, Google Scholar
• Arthur D, Vassilvitskii S (2007) K-means++ the advantages of careful seeding. Gabow H, ed. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1027–1035.Google Scholar
• Bacchus F, Hyttinen A, Järvisalo M, Saikko P (2017) Reduced cost fixing in MaxSAT. Beck JC, ed. Principles Practice Constraint Programming 23rd Internat. Conf. CP 2017 (Springer, Berlin), 641–651.Google Scholar
• Bajgiran OS, Cire AA, Rousseau LM (2017) A first look at picking dual variables for maximizing reduced cost fixing. Salvagnin D, Lombardi M, eds. Integration AI OR Techniques Constraint Programming 14th Internat. Conf. CPAIOR 2017 (Springer, Berlin), 221–228.Google Scholar
• Balas E, Carrera MC (1996) A dynamic subgradient-based branch-and-bound procedure for set covering. Oper. Res. 44(6):875–890.Link, Google Scholar
• Balas E, Saltzman MJ (1991) An algorithm for the three-index assignment problem. Oper. Res. 39(1):150–161.Link, Google Scholar
• Baldacci R, Bartolini E, Mingozzi A (2011a) An exact algorithm for the pickup and delivery problem with time windows. Oper. Res. 59(2):414–426.Link, Google Scholar
• Baldacci R, Christofides N, Mingozzi A (2008) An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Programming 115(2):351–385.Crossref, Google Scholar
• Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52(5):723–738.Link, Google Scholar
• Baldacci R, Mingozzi A, Calvo RW (2011d) An exact method for the capacitated location-routing problem. Oper. Res. 59(5):1284–1296.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011c) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2012) New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS J. Comput. 24(3):356–371.Link, Google Scholar
• Baldacci R, Bartolini E, Mingozzi A, Valletta A (2011b) An exact algorithm for the period routing problem. Oper. Res. 59(1):228–241.Link, Google Scholar
• Baldacci R, Mingozzi A, Roberti R, Calvo RW (2013) An exact algorithm for the two-echelon capacitated vehicle routing problem. Oper. Res. 61(2):298–314.Link, 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
• Bixby RE (2002) Solving real-world linear programs: A decade and more of progress. Oper. Res. 50(1):3–15.Link, Google Scholar
• Bixby ER, Fenelon M, Gu Z, Rothberg E, Wunderling R (2000) MIP: Theory and practice—closing the gap. Powell MJD, Scholtes S, eds. System Model. Optim. CMSO 1999 (Springer, Boston), 19–49.Google Scholar
• Bradley PS, Fayyad UM (1998) Refining initial points for k-means clustering. Shavlik JW, ed. Proc. 15th Internat. Conf. Machine Learn. (Morgan Kaufmann Publishers Inc., San Francisco), 91–99.Google Scholar
• Breugem T, Dollevoet T, Huisman D (2022) Is equality always desirable? Analyzing the trade-off between fairness and attractiveness in crew rostering. Management Sci. 68(4):2619–2641.Link, Google Scholar
• Cappanera P, Gallo G (2004) A multicommodity flow approach to the crew rostering problem. Oper. Res. 52(4):583–596.Link, Google Scholar
• Cattaruzza D, Absi N, Feillet D (2016a) The multi-trip vehicle routing problem with time windows and release dates. Transportation Sci. 50(2):676–693.Link, Google Scholar
• Cattaruzza D, Absi N, Feillet D (2016b) Vehicle routing problems with multiple trips. 4OR 14(3):223–259.Crossref, Google Scholar
• Celebi ME, Kingravi HA, Vela PA (2013) A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert Systems Appl. 40(1):200–210.Crossref, Google Scholar
• Cheng C, Adulyasak Y, Rousseau LM (2020) Drone routing with energy function: Formulation and exact algorithm. Transportation Res. Part B Methodological 139:364–387.Crossref, Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12:129–146.Crossref, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Crainic TG, Maggioni F, Perboli G, Rei W (2018) Reduced cost-based variable fixing in two-stage stochastic programming. Ann. Oper. Res. 1–37.Google Scholar
• Crowder H, Johnson EL, Padberg M (1983) Solving large-scale zero-one linear programming problems. Oper. Res. 31(5):803–834.Link, Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, Google Scholar
• Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Amer. 2(4):393–410.Link, Google Scholar
• de Lima VL, Iori M, Miyazawa FK (2023) Exact solution of network flow models with strong relaxations. Math. Programming 197(2):813–846.Crossref, Google Scholar
• Desaulniers G, Gschwind T, Irnich S (2020) Variable fixing for two-arc sequences in branch-price-and-cut algorithms on path-based models. Transportation Sci. 54(5):1170–1188.Link, Google Scholar
• Desaulniers G, Rakke JG, Coelho LC (2016b) A branch-price-and-cut algorithm for the inventory-routing problem. Transportation Sci. 50(3):1060–1076.Link, Google Scholar
• Desaulniers G, Errico F, Irnich S, Schneider M (2016a) Exact algorithms for electric vehicle-routing problems with time windows. Oper. Res. 64(6):1388–1405.Link, Google Scholar
• Engineer FG, Furman KC, Nemhauser GL, Savelsbergh MW, Song JH (2012) A branch-price-and-cut algorithm for single-product maritime inventory routing. Oper. Res. 60(1):106–122.Link, Google Scholar
• Ford LR, Fulkerson DR (1958) A suggested computation for maximal multi-commodity network flows. Management Sci. 5(1):97–101.Link, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, Poggi de Aragão M, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106:491–511.Crossref, Google Scholar
• Gurobi Optimization, LLC (2023) Gurobi Optimizer Reference Manual (Gurobi Optimization, LLC, Beaverton, OR).Google Scholar
• Hernandez F, Feillet D, Giroudeau R, Naud O (2014) A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration. 4OR 12(3):235–259.Crossref, Google Scholar
• Hernandez F, Feillet D, Giroudeau R, Naud O (2016) Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows. Eur. J. Oper. Res. 249(2):551–559.Crossref, Google Scholar
• Holmberg K, Yuan D (2000) A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Oper. Res. 48(3):461–481.Link, Google Scholar
• Homberger J, Gehring H (2005) A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. Eur. J. Oper. Res. 162(1):220–238.Crossref, Google Scholar
• Hooker JN, Ottosson G, Thorsteinsson ES, Kim HJ (1999) On integrating constraint propagation and linear programming for combinatorial optimization. Proc. Sixteenth National Conf. Artificial Intelligence (Orlando, Florida), 136–141.Google Scholar
• Irnich S, Desaulniers G, Desrosiers J, Hadjar A (2010) Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS J. Comput. 22(2):297–313.Link, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Johnson EL, Kostreva MM, Suhl UH (1985) Solving 0-1 integer programming problems arising from large scale planning models. Oper. Res. 33(4):803–819.Link, Google Scholar
• Kohl N, Desrosiers J, Madsen OB, Solomon MM, Soumis F (1999) 2-path cuts for the vehicle routing problem with time windows. Transportation Sci. 33(1):101–116.Link, Google Scholar
• Land AH, Doig AG (2010) An automatic method for solving discrete programming problems. 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), 105–132.Crossref, Google Scholar
• Laporte G, Nobert Y (1983) A branch and bound algorithm for the capacitated vehicle routing problem. Oper. Res. Spektrum 5:77–85.Crossref, Google Scholar
• Liguori PH, Mahjoub AR, Marques G, Sadykov R, Uchoa E (2023) Nonrobust strong knapsack cuts for capacitated location routing and related problems. Oper. Res. 71(5):1577–1595.Link, Google Scholar
• Lima I, Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A, Oliveira D, Queiroga E (2014) CVRPLIB: Capacitated vehicle routing problem library. http://vrp.galgos.inf.puc-rio.br/index.php/en/.Google Scholar
• Lloyd S (1982) Least squares quantization in PCM. IEEE Trans. Inform. Theory 28(2):129–137.Crossref, Google Scholar
• Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100:423–445.Crossref, Google Scholar
• Marques G, Sadykov R, Deschamps JC, Dupas R (2020) An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem. Comput. Oper. Res. 114:104833.Crossref, Google Scholar
• Mingozzi A, Roberti R, Toth P (2013) An exact algorithm for the multitrip vehicle routing problem. INFORMS J. Comput. 25(2):193–207.Link, Google Scholar
• Paradiso R, Roberti R, Laganá D, Dullaert W (2020) An exact solution framework for multitrip vehicle-routing problems with time windows. Oper. Res. 68(1):180–198.Link, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017a) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017b) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100.Crossref, Google Scholar
• Pessoa A, Uchoa E, Poggi de Aragão M (2009) A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks 54(4):167–177.Crossref, 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
• Pessoa A, Uchoa E, de Aragão MP, Rodrigues R (2010) Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2:259–290.Crossref, Google Scholar
• Posta M, Ferland JA, Michelon P (2012) An exact method with variable fixing for solving the generalized assignment problem. Comput. Optim. Appl. 52:629–644.Crossref, Google Scholar
• Quesnel F, Desaulniers G, Soumis F (2020) Improving air crew rostering by considering crew preferences in the crew pairing problem. Transportation Sci. 54(1):97–114.Link, Google Scholar
• Roberti R, Ruthmair M (2021) Exact methods for the traveling salesman problem with drone. Transportation Sci. 55(2):315–335.Link, Google Scholar
• Roboredo M, Sadykov R, Uchoa E (2023) Solving vehicle routing problems with intermediate stops using VRPSolver models. Networks 81(3):399–416.Crossref, Google Scholar
• Sadykov R, Uchoa E, Pessoa A (2021) A bucket graph–based labeling algorithm with application to vehicle routing. Transportation Sci. 55(1):4–28.Link, Google Scholar
• Sellmann M (2004) Theoretical foundations of CP-based Lagrangian relaxation. Wallace M, ed. Principles Practice Constraint Programming CP 2004 (Springer, Berlin), 634–647.Google Scholar
• Uchoa E, Pecin D, Pessoa A, Poggi M, Vidal T, Subramanian A (2017) New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257(3):845–858.Crossref, Google Scholar
• Wolsey LA, Nemhauser GL (1999) Integer and Combinatorial Optimization (John Wiley & Sons, New York).Google Scholar
• Yang Y (2023) An exact price-cut-and-enumerate method for the capacitated multitrip vehicle routing problem with time windows. Transportation Sci. 57(1):230–251.Link, Google Scholar
• You Z, Yang Y, Wang X, Yin W (2023) Two-stage learning to branch in branch-price-and-cut algorithms for solving vehicle routing problems exactly. Preprint, submitted November 13, http://dx.doi.org/10.2139/ssrn.4630549.Google Scholar
• Yunes T, Aron ID, Hooker JN (2010) An integrated solver for optimization problems. Oper. Res. 58(2):342–356.Link, Google Scholar
• Zhang S (2022) Solving the capacitated multi-trip vehicle routing problem with time windows. MPhil thesis, Hong Kong Polytechnic University, Hong Kong.Google Scholar