Stabilized Column Generation Via the Dynamic Separation of Aggregated Rows

References

• Andriluka M, Pishchulin L, Gehler PBS (2014) 2D human pose estimation: New benchmark and state of the art analysis. Proc. 27th Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 3686–3693.Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463.Link, Google Scholar
• Ben Amor HMT, Desrosiers J, Frangioni A (2009) On the choice of explicit stabilizing terms in column generation. Discrete Appl. Math. 157(6):1167–1184.Crossref, Google Scholar
• Boland N, Dethridge J, Dumitrescu I (2006) Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper. Res. Lett. 34:58–68.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
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1–20.Crossref, Google Scholar
• Desaulniers G, Lessard F, Hadjar A (2008) Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows. Transportation Sci. 42(3):387–404.Link, Google Scholar
• Desrosiers J, Gauthier JB, Lübbecke ME (2014) Row-reduced column generation for degenerate master problems. Eur. J. Oper. Res. 236(2):453–460.Crossref, Google Scholar
• Deveci M, Demirel NÇ (2018) A survey of the literature on airline crew scheduling. Engrg. Appl. Artificial Intelligence 74:54–69.Crossref, Google Scholar
• Elhallaoui I, Metrane A, Desaulniers G, Soumis F (2011) An improved primal simplex algorithm for degenerate linear programs. INFORMS J. Comput. 23(4):569–577.Link, Google Scholar
• Elhallaoui I, Villeneuve D, Soumis F, Desaulniers G (2005) Dynamic aggregation of set-partitioning constraints in column generation. Oper. Res. 53(4):632–645.Link, Google Scholar
• Elhedhli S, Li L, Gzara M, Naoum-Sawaya J (2011) A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS J. Comput. 23(3):404–415.Link, Google Scholar
• Felzenszwalb PF, Girshick RB, McAllester D, Ramanan D (2010) Object detection with discriminatively trained part-based models. IEEE Trans. Pattern Anal. Machine Intelligence 32(9):1627–1645.Crossref, Google Scholar
• Fernandes Muritiba AE, Iori M, Malaguti E, Toth P (2010) Algorithms for the bin packing problem with conflicts. INFORMS J. Comput. 22(3):401–415.Link, Google Scholar
• Gauthier JB, Desrosiers J, Lübbecke ME (2016) Tools for primal degenerate linear programs: IPS, DCA, and PE. EURO J. Transportation Logist. 5(2):161–204.Crossref, Google Scholar
• Gehring H, Homberger J (2001) A parallel two-phase metaheuristic for routing problems with time windows. Asia-Pacific J. Oper. Res. 18(1):35.Google Scholar
• Gendreau M, Laporte G, Semet F (2004) Heuristics and lower bounds for the bin packing problem with conflicts. Comput. Oper. Res. 31(3):347–358.Crossref, Google Scholar
• Gschwind T, Irnich S (2016) Dual inequalities for stabilized column generation revisited. INFORMS J. Comput. 28(1):175–194.Link, Google Scholar
• Haghani N, Contardo C, Yarkony J (2020) Relaxed dual optimal inequalities for relaxed columns: With application to vehicle routing. Preprint, submitted April 11, https://arxiv.org/abs/2004.05499.Google Scholar
• Haghani N, Contardo C, Yarkony J (2021) Smooth and flexible dual optimal inequalities. INFORMS J. Optim. ForthcomingGoogle Scholar
• Insafutdinov E, Pishchulin L, Andres B, Andriluka M, Schiele B (2016) Deepercut: A deeper, stronger, and faster multi-person pose estimation model. Leibe B, Matas J, Sebe N, Welling M, eds. Proc. 14th Eur. Conf. Comput. Vision, Lecture Notes in Computer Science, vol. 9910 (Springer, Cham), 34–50.Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation, 1st ed. (Sprinter, Boston), 33–65.Crossref, Google Scholar
• Lokhande VS, Wang S, Singh M, Yarkony J (2020) Accelerating column generation via flexible dual optimal inequalities with application to entity resolution. Proc. AAAI Conf. Artificial Intelligence 34(2):1593–5520.Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Marsten RE, Hogan WW, Blankenship JW (1975) The boxstep method for large-scale optimization. Oper. Res. 23(3):389–405.Link, Google Scholar
• Neame PJ (1999) Nonsmooth dual methods in integer programming. PhD thesis, Department of Mathematics and Statistics, University of Melbourne, Melbourne, VIC, Australia.Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2018) Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2):339–360.Link, Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3:255–273.Crossref, Google Scholar
• Righini G, Salani M (2008) New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51:155–170.Crossref, Google Scholar
• Rousseau LM, Gendreau M, Feillet D (2007) Interior point stabilization for column generation. Oper. Res. Lett. 35(5):660–668.Crossref, Google Scholar
• Sadykov R, Vanderbeck F (2013) Bin packing with conflicts: A generic branch-and-price algorithm. INFORMS J. Comput. 25(2):244–255.Link, Google Scholar
• Wang S, Ihler A, Kording K, Yarkony J (2018) Accelerating dynamic programs via nested benders decomposition with application to multi-person pose estimation. Ferrari V, Hebert M, Sminchisescu C, Weiss Y, eds. Proc. 15th Eur. Conf. Comput. Vision, Lecture Notes in Computer Science, vol. 11218 (Springer, Cham), 677–692.Google Scholar
• Wentges P (1997) Weighted Dantzig-Wolfe decomposition for linear mixed-integer programming. Internat. Trans. Oper. Res. 4(2):151–162.Crossref, Google Scholar
• Yarkony J, Adulyasak Y, Singh M, Desaulniers G (2020) Data association via set packing for computer vision applications. INFORMS J. Optim. 2(3):167–191.Link, Google Scholar
• Zaghrouti A, Soumis F, El Hallaoui I (2014) Integral simplex using decomposition for the set partitioning problem. Oper. Res. 62(2):435–449.Link, Google Scholar