Smooth and Flexible Dual Optimal Inequalities

References

• Barahona F, Jensen D (1998) Plant location with minimum inventory. Math. Programming 83(1):101–112.Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1996) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.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
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik 4(1):238–252.Google Scholar
• Briant O, Lemaréchal C, Meurdesoif P, Michel S, Perrot N, Vanderbeck F (2008) Comparison of bundle and classical column generation. Math. Programming 113(2):299–344.Google Scholar
• Contreras IA, Cordeau J, Laporte G (2011) Benders decomposition for large-scale uncapacitated hub location. Oper. Res. 59(6):1477–1490.Link, 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
• Diaz J, Fernández E (2002) A branch-and-price algorithm for the single source capacitated plant location problem. J. Oper. Res. Soc. 53(7):728–740.Google Scholar
• Du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1-3):229–237.Google Scholar
• Frangioni A (2002) Generalized bundle methods. SIAM J. Optim. 13(1):117–156.Google Scholar
• Geoffrion AM (1974) Lagrangean relaxation for integer programming. Balinski ML, ed. Approaches to Integer Programming, Mathematical Programming Studies, vol. 2 (Springer, Berlin), 82–114.Google Scholar
• Gilmore P, Gomory R (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Gondzio J, González-Brevis P (2015) A new warmstarting strategy for the primal-dual column generation method. Math. Programming 152(1-2):113–146.Google Scholar
• Gondzio J, González-Brevis P, Munari PA (2013) New developments in the primal-dual column generation technique. Eur. J. Oper. Res. 224(1):41–51.Google Scholar
• Gondzio J, González-Brevis P, Munari PA (2016) Large-scale optimization with the primal-dual column generation method. Math. Programming Comput. 8(1):47–82.Google Scholar
• Gschwind T, Irnich S (2016) Dual inequalities for stabilized column generation revisited. INFORMS J. Comput. 28(1):175–194.Link, Google Scholar
• Gschwind T, Irnich S (2017) Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities. OR Spectrum 39(2):541–556.Google Scholar
• Holmberg K, Rönnqvist M, Yuan D (1999) An exact algorithm for the capacitated facility location problems with single sourcing. Eur. J. Oper. Res. 113(3):544–559.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
• Keuper M, Singh M, Yarkony J (2019) Massively parallel benders decomposition for correlation clustering. Preprint, submitted February 15, https://arxiv.org/abs/1902.05659.Google Scholar
• Leal-Taixe L, Pons-Moll G, Rosenhahn B (2012) Branch-and-price global optimization for multi-view multi-target tracking. Proc. 25th Conf. Comput. Vision Pattern Recognition (IEEE, Piscataway, NJ), 1987–1994.Google Scholar
• Lokhande VS, Wang S, Singh M, Yarkony J (2020) Accelerating column generation via flexible dual optimal inequalities with application to entity resolution. ArXiv preprint, revised February 21, https://arxiv.org/abs/1909.05460.Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Magnanti TL, Wong RT (1981) Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29(3):464–484.Link, Google Scholar
• Marsten RE, Hogan W, Blankenship JW (1975) The boxstep method for large-scale optimization. Oper. Res. 23(3):389–405.Link, Google Scholar
• Martinelli R, Pecin D, Poggi M (2014) Efficient elementary and restricted non-elementary route pricing. Eur. J. Oper. Res. 239(1):102–111.Google Scholar
• Mitchell JE (1994) An interior point column generation method for linear programming using shifted barriers. SIAM J. Optim. 4(2):423–440.Google Scholar
• Pessoa AA, 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
• Pisinger D (1997) A minimal algorithm for the 0-1 knapsack problem. Oper. Res. 45(5):758–767.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(3):255–273.Google Scholar
• Rousseau LM, Gendreau M, Feillet D (2007) Interior point stabilization for column generation. Oper. Res. Lett. 35(5):660–668.Google Scholar
• van Ackooij W, Frangioni A (2018) Incremental bundle methods using upper models. SIAM J. Optim. 28(1):379–410.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 Comput. Sci., vol. 11218 (Springer, Cham, Switzerland), 652–666.Google Scholar
• Wang S, Wolf S, Fowlkes C, Yarkony J (2017) Tracking objects with higher order interactions via delayed column generation. Singh A, Zhu J, eds. Proc. 20th Internat. Conf. Artificial Intelligence Statist., Proc. Machine Learn. Res., vol. 54 (JMLR, Fort Lauderdale, FL), 1132–1140.Google Scholar
• Yang Z, Chu F, Chen H (2012) A cut-and-solve based algorithm for the single-source capacitated facility location problem. Eur. J. Oper. Res. 221(3):521–532.Google Scholar
• Yarkony J, Fowlkes C (2015) Planar ultrametrics for image segmentation. Cortes C, Lee DD, Sugiyama M, Garnett R, eds. NIPS’15 Proc. 28th Internat. Conf. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 64–72.Google Scholar
• Yarkony J, Ihler A, Fowlkes C (2012) Fast planar correlation clustering for image segmentation. Fitzgibbon A, Lazebnik S, Perona P, Sato Y, Schmid C, eds. Proc. 12th Eur. Conf. Comput. Vision, Lecture Notes in Comput. Sci., vol. 7577 (Springer, Berlin), 1169–1176.Google Scholar
• Yarkony J, Adulyasak Y, Singh M, Desaulniers G (2019) Data Association via Set Packing for Computer Vision Applications (Les Cahiers du GERAD, Montreal).Google Scholar
• Zetina CA, Contreras IA, Cordeau J (2019) Exact algorithms based on benders decomposition for multicommodity uncapacitated fixed-charge network design. Comput. OR 111:311–324.Google Scholar