Ph.D. Course on "Column generation and related topics for hard combinatorial problems"

School of Graduate Studies G. Galilei

J.M. Valério de Carvalho

Place: Dipartimento di Informatica, Università di Pisa, Pisa, Italy

Date: April 20 - 24, 2009

Timetable

Contact person: A. Frangioni

Programme

Pre-requisites: Linear Programming (LP); duality

Contents:

Bibliography

Books

R.K. Ahuja, T. Magnanti and J.B. Orlin, "Network flows: Theory, Algorithms and Applications". Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1993.

S. Martello and P. Toth "Knapsack Problems: Algorithms and Computer Implementations", Wiley, New York, 1990.

G.L. Nemhauser and L.A. Wolsey, "Integer and Combinatorial Optimization", Wiley Interscience, 1988.

H. Ben Amor and J.M. Valério de Carvalho, "Cutting Stock Problems", in "Column Generation", G. Desaulniers, J. Desrosiers and M.M. Solomon (eds.), 131-162, Springer, 2005.

Papers:

C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh and P.H. Vance, "Branch-and-Price: Column Generation for Solving Huge Integer Programs", Operations Research 46(3), 316-329, 1998.

H. Ben Amor, J. Desrosiers and A. Frangioni "On the Choice of Explicit Stabilizing Terms in Column Generation", Discrete Applied Mathematics, to appear, 2009.

O. Briant, C. Lemaréchal, Ph. Meurdesoif, S. Michel, N. Perrot, and F. Vanderbeck, "Comparison of bundle and classical column generation", Mathematical Programming 113(2), 299-344, 2008.

S. Fekete and J. Schepers, "New classes of fast lower bounds for bin packing problems". Mathematical Programming 91, 11-31, 2001.

A. Frangioni "About Lagrangian Methods in Integer Optimization" Annals of Operations Research 139, 163-193, 2005.

A. Frangioni "Generalized Bundle Methods" SIAM Journal on Optimization 13(1), 117-156, 2002.

O. du Merle, D. Villeneuve, J. Desrosiers and P. Hansen, "Stabilized column generation", Discrete Mathematics 194, 229-297, 1999.

F. Vanderbeck, "Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem". Operations Research 48(6), 915-926, 2000.

F. Clautiaux, C. Alves and J.M. Valério de Carvalho, "A survey of dual-feasible and superadditive functions", to appear in Annals of Operations Research, 2009.

C. Alves and J.M. Valério de Carvalho, "A branch-and-price-and-cut algorithm for the pattern minimization problem", RAIRO Operations Research, 42, 435-453, 2008.

C. Alves and J.M. Valério de Carvalho, "A Stabilized Branch-and-Price-and-Cut Algorithm for the Multiple Length Cutting Stock Problem", Computers and Operations Research 35(4), 1315-1328, 2008.

F. Alvelos and J.M. Valério de Carvalho, "An extended model and a column generation algorithm for the planar multicommodity flow problem", Networks 50(1), 3-16, 2007.

M. Pereira Lopes and J.M. Valério de Carvalho, "A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times", European Journal of Operational Research 176(3), 1508-1527, 2007.

C. Alves and J.M. Valério de Carvalho, "Accelerating Column Generation for Variable Sized Bin-Packing Problems", European Journal of Operational Research 183(3), 1333-1352, 2007.

H. Ben Amor, J. Desrosiers and J.M. Valério de Carvalho, "Dual-optimal Inequalities for Stabilized Column Generation", Operations Research 54(3), 454--463, 2006.

H. Ben Amor and J.M. Valério de Carvalho, "Cutting Stock Problems", in Column Generation, Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon (eds.), Springer, 2005.

J.M. Valério de Carvalho, "Using extra dual cuts to accelerate convergence in column generation", INFORMS Journal on Computing 17(2), 175-182, 2005.

J.M. Valério de Carvalho, "LP Models for Bin-Packing and Cutting Stock Problems", European Journal of Operational Research 141(2), 253-273, 2002.

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