A Primer in Column Generation

• Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice-Hall, Inc., Englewood Cliffs, New Jersey.

  Google Scholar 

• Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., and Vance, P.H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3):316–329.

  MathSciNet  Google Scholar 

• Ben Amor, H. and Desrosiers, J. (2003). A proximal trust region algorithm for column generation stabilization. Les Cahiers du GERAD G-2003-43, HEC, Montréal, Canada. Forthcoming in: Computers & Operations Research.

  Google Scholar 

• Ben Amor, H., Desrosiers, J., and Valério de Carvalho, J.M. (2003). Dual-optimal inequalities for stabilized column generation. Les Cahiers du GERAD G-2003-20, HEC, Montréal, Canada.

  Google Scholar 

• Ben Amor, H. and Valério de Carvalho, J.M. (2004). Cutting stock problems. In this book.

  Google Scholar 

• Dantzig, G.B. and Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8:101–111.

  Google Scholar 

• Desaulniers, G., Desrosiers, J., Ioachim, I., Solomon, M.M., Soumis, F., and Villeneuve, D. (1998). A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In: Fleet Management and Logistics (T.G. Crainic and G. Laporte, eds.), pp. 57–93, Kluwer, Norwell, MA.

  Google Scholar 

• Desaulniers, G., Desrosiers, J., and Solomon, M.M. (2001). Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems. In: Essays and Surveys in Metaheuristics (C.C. Ribeiro and P. Hansen, eds.), pp. 309–324, Kluwer, Boston.

  Google Scholar 

• du Merle, O., Villeneuve, D., Desrosiers, J., and Hansen, P. (1999). Stabilized column generation. Discrete Mathematics, 194:229–237.

  Article  MathSciNet  Google Scholar 

• Elhallaoui, I., Villeneuve, D., Soumis, F., and Desaulniers, G. (2003). Dynamic aggregation of set partitioning constraints in column generation. Les Cahiers du GERAD G-2003-45, HEC, Montréal, Canada. Forthcoming in: Operations Research.

  Google Scholar 

• Ford, L.R. and Fulkerson, D.R. (1958). A suggested computation for maximal multicommodity network flows. Management Science, 5:97–101.

  MathSciNet  Google Scholar 

• Geoffrion, A.M. (1974). Lagrangean relaxation for integer programming. Mathematical Programming Study (Series), 2:82–114.

  MATH  MathSciNet  Google Scholar 

• Gilmore, P.C. and Gomory, R.E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9:849–859.

  MathSciNet  Google Scholar 

• Gilmore, P.C. and Gomory, R.E. (1963). A linear programming approach to the cutting stock problem. Part II. Operations Research, 11:863–888.

  Google Scholar 

• Goffin, J.-L. and Vial, J.-Ph. (1999). Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method. Technical Report 99.02, Logilab, Université de Genève. Forthcoming in: Optimization Methods & Software.

  Google Scholar 

• Guignard, M. (2004). Lagrangean relaxation. In: Handbook of Applied Optimization (M. Resende and P. Pardalos, eds.), Oxford University Press.

  Google Scholar 

• Hiriart-Urruty, J.-B. and Lemaréchal, C. (1993). Convex Analysis and Minimization Algorithms, Part 2: Advanced Theory and Bundle Methods, volume 306, Grundlehren der mathematischen Wissenschaften, Springer, Berlin.

  Google Scholar 

• Kantorovich, L. (1960). Mathematical methods of organising and planning production. Management Science, 6:366–422.

  MATH  MathSciNet  Google Scholar 

• Kelley Jr., J.E. (1961). The cutting-plane method for solving convex programs. Journal of the Society for Industrial and Applied Mathematics, 8(4):703–712.

  Article  MATH  MathSciNet  Google Scholar 

• Lasdon, L.S. (1970). Optimization Theory for Large Systems. Macmillan, London.

  Google Scholar 

• Lübbecke, M.E. and Desrosiers, J. (2002). Selected topics in column generation. Les Cahiers du GERAD G-2002-64, HEC, Montréal, Canada. Forthcoming in: Operations Research.

  Google Scholar 

• Nemhauser, G.L. and Wolsey, L.A. (1988). Integer and Combinatorial Optimization. John Wiley & Sons, Chichester.

  Google Scholar 

• Mamer, J.W. and McBride, R.D. (2000). A decomposition-based pricing procedure for large-scale linear programs—An application to the linear multicommodity flow problem. Management Science, 46(5):693–709.

  Article  Google Scholar 

• Marsten, R.E. (1975). The use of the boxstep method in discrete optimization. Mathematical Programming Study, 3:127–144.

  MATH  Google Scholar 

• Marsten, R.E., Hogan, W.W., and Blankenship, J.W. (1975). The Boxstep method for large-scale optimization. Operations Research, 23:389–405.

  MathSciNet  Google Scholar 

• Poggi de Aragão, M. and Uchoa, E. (2003). Integer program reformulation for robust branch-and-cut-and-price algorithms. In: Proceedings of the Conference Mathematical Program in Rio: A Conference in Honor of Nelson Maculan, pp. 56–61.

  Google Scholar 

• Schrijver, A. (1986). Theory of Linear and Integer Programming. John Wiley & Sons, Chichester.

  Google Scholar 

• Valério de Carvalho, J.M. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86:629–659.

  Article  MATH  MathSciNet  Google Scholar 

• Valério de Carvalho, J.M. (2002). LP models for bin-packing and cutting stock problems. European Journal of Operational Research, 141(2):253–273.

  Article  MATH  MathSciNet  Google Scholar 

• Valério de Carvalho, J.M. (2003). Using extra dual cuts to accelerate convergence in column generation. Forthcoming in: INFORMS Journal of Computing.

  Google Scholar 

• Vanderbeck, F. (2000). On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research, 48(1):111–128.

  Article  MATH  MathSciNet  Google Scholar 

• Vanderbeck, F. (2004). Implementing mixed integer column generation. In this book.

  Google Scholar 

• Vanderbeck, F. and Wolsey, L.A. (1996). An exact algorithm for IP column generation. Operations Research Letters, 19:151–159.

  Article  MathSciNet  Google Scholar 

• Villeneuve, D., Desrosiers, J., Lübbecke, M.E., and Soumis, F. (2003). On compact formulations for integer programs solved by column generation. Les Cahiers du GERAD G-2003-06, HEC, Montréal, Canada. Forthcoming in: Annals of Operations Research.

  Google Scholar 

• Walker, W.E. (1969). A method for obtaining the optimal dual solution to a linear program using the Dantzig-Wolfe decomposition. Operations Research, 17:368–370.

  Article  MATH  MathSciNet  Google Scholar 

Download references