Dual Inequalities for Stabilized Column Generation Revisited

References

• Alves C, Valério de Carvalho JM (2008) A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem. Comp. Oper. Res. 35(4):1315–1328.Crossref, Google Scholar
• Alves C, Valério de Carvalho J, Clautiaux F, Rietz J (2014) Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem. Eur. J. Oper. Res. 233(1):43–63.Crossref, Google Scholar
• Balas E, Padberg MW (1976) Set partitioning: A survey. SIAM Rev. 18(4):710–760.Crossref, Google Scholar
• Balas E, Xue J (1991) Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs. SIAM J. Comput. 20(2):209–221.Crossref, Google Scholar
• Balinski ML (1965) Integer programming: Methods, uses, computation. Management Sci. 12(3):253–313.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) 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
• Ben Amor H, Valério de Carvalho J (2005) Cutting stock problems. Desaulniers G, Desrosiers J, Solomon M, eds. Column Generation (Springer, New York), 131–161.Crossref, Google Scholar
• Bettinelli A, Cacchiani V, Malaguti E (2014) Bounds and algorithms for the knapsack problem with conflict graph. Technical Report OR-14-16, DEIS—University of Bologna, Bologna, Italy.Google Scholar
• Bianchessi N, Archetti C, Speranza MG (2014) An exact solution approach for the split commodities mixed routing problem. Presentation, VeRoLog Conference Oslo, Norway.Google Scholar
• Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182.Link, Google Scholar
• Caprara A, Toth P (2001) Lower bounds and algorithms for the 2-dimensional vector packing problem. Disc. Appl. Math. 111(3):231–262.Crossref, 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
• Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6):375–382.Crossref, Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, Google Scholar
• Desaulniers G, Desrosiers J, Ioachim I, Solomon M, Soumis F, Villeneuve D (1998) A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. Crainic T, Laporte G, eds. Fleet Management and Logistics (Kluwer Academic Publisher, Boston), 57–93.Crossref, 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
• du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Disc. Math. 194(1–3):229–237.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
• Fréville A (2004) The multidimensional 0-1 knapsack problem: An overview. Eur. J. Oper. Res. 155(1):1–21.Crossref, Google Scholar
• Garfinkel RS, Nemhauser GL (1969) The set-partitioning problem: Set covering with equality constraints. Oper. Res. 17(5):848–856.Link, Google Scholar
• Gauthier JB, Desrosiers J, Lübbecke ME (2015) Tools for primal degenerate linear programs: IPS, DCA, and PE. EURO J. Transportation Logist., ePub ahead of print March 27, http://dx.doi.org/10.1007/s13676-015-0077-5.Google Scholar
• Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Gilmore PC, Gomory RE (1963) A linear programming approach to the cutting stock problem—Part II. Oper. Res. 11(6):863–888.Link, Google Scholar
• Gschwind T, Irnich S (2014) Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities. Technical Report LM-2014-06, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Mainz, Germany.Google Scholar
• Gualandi S, Chiarandini M (2014) Graph coloring benchmarks. Accessed January 25, 2016, https://sites.google.com/site/graphcoloring/home.Google Scholar
• Gualandi S, Malucelli F (2012) Exact solution of graph coloring problems via constraint programming and column generation. INFORMS J. Comput. 24(1):81–100.Link, Google Scholar
• Held S, Cook W, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• Hifi M, Michrafy M (2007) Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Comp. Oper. Res. 34(9):2657–2673.Crossref, Google Scholar
• Hiriart-Urruty J-B, Lemaréchal C (1993) Convex Analysis and Minimization Algorithms, Part 2: Advanced Theory and Bundle Methods, Grundlehren der Mathematischen Wissenschaften, Vol. 306 (Springer, Berlin).Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon M, eds. Column Generation (Springer, New York), 33–65.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin).Crossref, Google Scholar
• Lee C, Park S (2011) Chebyshev center based column generation. Disc. Appl. Math. 159(18):2251–2265.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Malaguti E, Monaci M, Toth P (2011) An exact approach for the vertex coloring problem. Disc. Opt. 8(2):174–190.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
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations, Wiley Intersience Series in Discrete Mathematics and Optimization (Wiley, New York).Google Scholar
• Mehrotra A, Trick MA (1996) A column generation approach for graph coloring. INFORMS J. Comput. 8(4):344–354.Link, Google Scholar
• Méndez-Díaz I, Zabala P (2006) A branch-and-cut algorithm for graph coloring. Disc. Appl. Math. 154(5):826–847.Crossref, Google Scholar
• Östergård PRJ (2002) A fast algorithm for the maximum clique problem. Disc. Appl. Math. 120(1–3):197–207.Crossref, Google Scholar
• Ozden M (1988) A solution procedure for general knapsack problems with a few constraints. Comp. Oper. Res. 15(2):145–155.Crossref, Google Scholar
• Pattillo J, Youssef N, Butenko S (2013) On clique relaxation models in network analysis. Eur. J. Oper. Res. 226(1):9–18.Crossref, Google Scholar
• Pferschy U, Schauer J (2009) The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2):233–249.Crossref, Google Scholar
• Rousseau L-M, 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
• Scholl A, Klein R, Jürgens C (1997) Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comp. Oper. Res. 24(7):627–645.Crossref, Google Scholar
• Sim K, Hart E (2013) Generating single and multiple cooperative heuristics for the one dimensional bin packing problem using a single node genetic programming island model. Proc. 15th Ann. Conf. Genetic Evolutionary Comput. (ACM, New York),1549–1556.Crossref, Google Scholar
• Valério de Carvalho JM (1998) Exact solution of cutting stock problems using column generation and branch-and-bound. Internat. Trans. Oper. Res. 5(1):35–44.Crossref, Google Scholar
• Valério de Carvalho JM (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res. 86:629–659.Crossref, Google Scholar
• Valério de Carvalho JM (2005) Using extra dual cuts to accelerate column generation. INFORMS J. Comput. 17(2):175–182.Link, Google Scholar
• Vance P, Barnhart C, Johnson E, Nemhauser G (1994) Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. Appl. 3(2):111–130.Crossref, Google Scholar
• Vanderbeck F (1999) Computational study of a column generation algorithm for bin packing and cutting stock problems. Math. Programming 86(3):565–594.Crossref, 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
• Vanderbeck F (2005) Implementing mixed integer column generation. Desaulniers G, Desrosiers J, Solomon M, eds. Column Generation (Springer, New York), 331–358.Crossref, Google Scholar