Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation

References

• 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
• Barahona F, Anbil R (2000) The volume algorithm: Producing primal solutions with a subgradient method. Math. Programming 87(3):385–399.Crossref, Google Scholar
• Beasley JE (1990) OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Ben-Ameur W, Neto J (2007) Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks 49(1):3–17.Crossref, 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
• 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.Crossref, Google Scholar
• Camerini PM, Fratta L, Maffioli F (1975) On improving relaxation methods by modified gradient techniques. Balinski ML, Wolfe P, eds. Nondifferentiable Optimization (Springer, Berlin), 26–34.Crossref, Google Scholar
• Côté M-C, Gendron B, Rousseau L-M (2013) Grammar-based column generation for personalized multi-activity shift scheduling. INFORMS J. Comput. 25(3):461–474.Link, Google Scholar
• Demassey S, Pesant G, Rousseau L-M (2006) A cost-regular based hybrid column generation approach. Constraints 11(4):315–333.Crossref, Google Scholar
• de Oliveira W, Sagastizábal C (2014) Level bundle methods for oracles with on-demand accuracy. Optim. Methods Software 29(6):1180–1209.Crossref, Google Scholar
• du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1–3):229–237.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
• Fischetti M, Salvagnin D (2010) An in-out approach to disjunctive optimization. Lodi A, Milano M, Toth P, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, Vol. 6140 (Springer, Berlin), 136–140.Crossref, Google Scholar
• Frangioni A, Gorgone E (2014) Bundle methods for sum-functions with “easy” components: Applications to multicommodity network design. Math. Programming 145(1):133–161.Crossref, Google Scholar
• Goffin J-L, Vial J-P (2002) Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method. Optim. Methods Software 17(5):805–867.Crossref, Google Scholar
• Gondzio J, González-Brevis P, Munari P (2013) New developments in the primal–dual column generation technique. Eur. J. Oper. Res. 224(1):41–51.Crossref, Google Scholar
• Johnson DJ, Trick MA, eds. (1996) Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop (American Mathematical Society, Boston).Google Scholar
• Kiwiel K (1990) Proximity control in bundle methods for convex nondifferentiable optimization. Math. Programming 46(1–3):105–122.Crossref, Google Scholar
• Lee C, Park S (2011) Chebyshev center based column generation. Discrete Appl. Math. 159(18):2251–2265.Crossref, Google Scholar
• Lemaréchal C, Nemirovskii A, Nesterov Y (1995) New variants of bundle methods. Math. Programming 69(1–3):111–147.Crossref, 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
• Munari P, Gondzio J (2013) Using the primal-dual interior point algorithm within the branch-price-and-cut method. Comput. Oper. Res. 40(8):2026–2036.Crossref, Google Scholar
• Neame PJ (2000) Nonsmooth Dual Methods in Integer Programming. PhD thesis, University of Melbourne, Department of Mathematics and Statistics, Melbourne.Google Scholar
• Östergård PRJ (2001) A new algorithm for the maximum-weight clique problem. Nordic J. Comput. 8(4):424–436.Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2013) In-out separation and column generation stabilization by dual price smoothing. Bonifaci V, Demetrescu C, Marchetti-Spaccamela A, eds. Symposium on Experimental Algorithms, Lecture Notes in Computer Science, Vol. 7933 (Springer, Boston), 354–365.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(3–4):259–290.Crossref, Google Scholar
• Pisinger D (1997) A minimal algorithm for the 0-1 knapsack problem. Oper. Res. 45(5):758–767.Link, Google Scholar
• Potts CN, Van Wassenhove LN (1985) A branch and bound algorithm for the total weighted tardiness problem. Oper. Res. 33(2):363–377.Link, Google Scholar
• Rey PA, Sagastizabal CA (2002) Dynamical adjustment of the prox-parameter in variable metric bundle methods. Optimization 51(2):423–447.Crossref, Google Scholar
• Sadykov R, Lazarev AA, Shiryaev V, Stratonnikov A (2013) Solving a freight railcar flow problem arising in Russia. Frigioni D, Stiller S, eds. 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, OpenAccess Series in Informatics (OASIcs), Vol. 33 (Schloss Dagstuhl–Leibniz-Zentrum Fuer Informatik, Dagstuhl, Germany), 55–67.Google Scholar
• Vanderbeck F (2002) Extending dantzig’s bound to the bounded multiple-class binary knapsack problem. Math. Programming 94(1):125–136.Crossref, Google Scholar
• Vanderbeck F (2005) Implementing mixed integer column generation. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, Boston), 331–358.Crossref, Google Scholar
• Vanderbeck F, Savelsbergh MWP (2006) A generic view of Dantzig-Wolfe decomposition in mixed integer programming. Oper. Res. Lett. 34(3):296–306.Crossref, 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
• Yagiura M, Ibaraki T, Glover F (2006) A path relinking approach with ejection chains for the generalized assignment problem. Eur. J. Oper. Res. 169(2):548–569.Crossref, Google Scholar
• Zangwill WI (1969) A backlogging model and a multi-echelon model of a dynamic economic lot size production system-a network approach. Management Sci. 15(9):506–527.Link, Google Scholar