IDENTIFICATION

Doctorate Course: Decomposition Methods in Integer Programming (Lecture_Notes.pdf)
Program(s): Programa Doutoral em Engenharia Industrial e de Sistemas (PDEIS) and Programa Doutoral em Matemática e Aplicações (PDMA)
Semester: course is offered in the 2^nd semester (February through July)

Language: english

Lecturer: J. M. Valério de Carvalho
Contacts: email: vc@dps.uminho.pt

tel.: +351 253 604 744
Department: Produção e Sistemas
School: Engenharia

SUBJECT DESCRIPTION AND OBJECTIVES

This course is intended for graduate students interested in column generation and its applications. Column generation is a very successful optimization technique for addressing large scale integer programming models that arise from real world applications, in areas such as logistics, transportation, scheduling and manufacturing.

It offers an introduction to the theory of decomposition, and covers the implementation of branch-and-price-and-cut algorithms for Cutting Stock (CSP), Bin Packing (BPP), Parallel machine scheduling and Vehicle routing. Other topics, as stabilization, cutting planes, and practical issues, as accelerating strategies and heuristics, are also addressed.

PRE-REQUISITES

Linear Programming (LP)

Duality

PROGRAM

0 - Introduction	Structure of course
1 - Decomposition methods	Strength of models in integer programming (IP) Dantzig-Wolfe decomposition (DW) Comparative strength of IP, DW and LP Application Example Lagrangean relaxation Lagrangean relaxation vs. DW decomposition Lower bounds
2 - Applications	Reasons for using decomposition Block angular structure: examples Solving LP relaxations with column generation: Application example: Cutting Stock (CSP) and Bin Packing (BPP) Problems Parallel machine scheduling Vehicle routing
3 - Branch-and-price algorithms	Partition and branching Compatibility between master and sub-problem Coping with changes in sub-problem Application with binary variables: generalized assignment problem Application with binary variables: parallel machine scheduling
4 - Branch-and-price algorithms (cont.)	Application with general integer variables: Arc-flow model for CSP and BPP Application example: cutting stock problem Multiple lengths CSP
5 - Stabilization	Primal and dual perspectives Stabilizing terms: examples Degeneracy and perturbation Perfect Dual Information (Weak and deep) dual-optimal inequalities Application: planar multicommodity flows Application: cutting stock problem
6 - Practical issues, accelerating strategies and heuristics	Pre-processing Master problem Subproblem Branch-and-bound
7 - Primal cutting planes	Separation and row generation Polyhedral approaches Row generation in column generation models: compatibility Application: multicommodity flow problem Super-additive Non-decreasing Functions and Dual Feasible Functions Strengthening column generation models Application: minimization of number of set-ups in CSP
8 - Heuristics	Quality of models and quality of heuristics Rounding heuristics Local search based on column generation Application: binary multicommodity flows

BIBLIOGRAPHY

BOOKS

Nemhauser and Wolsey, Integer and Combinatorial Optimization, Wiley Interscience, 1999.

Column Generation, Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon (eds.), Springer, 2005.

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

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

BIBLIOGRAPHY

PAPERS

General

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

Hatem Ben Amor, J.M. Valério de Carvalho, Cutting Stock Problems, in Column Generation, Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon (eds.), Springer, 2005, XVI, ISBN: 0-387-25485-4

A. Frangioni "About Lagrangian methods in integer optimization" Annals of Operations Research 139, p. 163 - 193, 2005

Stabilization

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

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

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

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

Cláudio Alves, J.M. Valério de Carvalho, Accelerating column generation for variable sized bin-packing problems, European Journal of Operational Research, 183 (3) pp. 1333-1352, 2007.

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

Ben Amor, J. Desrosiers and A. Frangioni "On the choice of explicit stabilizing terms in column generation", Discrete Applied Mathematics 157, pp.1167-1184, 2009.

Dual Feasible Functions

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

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

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

François Clautiaux, Cláudio Alves, Jose Valério de Carvalho, A survey of dual-feasible and superadditive functions, Annals of Operations Research, 179, 1, pp. 317-342, 2010.

Applications

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

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

Manuel Pereira Lopes, 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) pp. 1508-1527, 2007.

Cláudio Alves, 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) pp. 1315-1328, 2008.

J. Desrosiers, Y. Dumas, M. Solomon, F. Soumis, Time constrained routing and scheduling. In Network Routing. M. Ball, T. Magnanti, C. Monma, G. Nemhauser (eds.), Amsterdam, Elsevier Science: pp. 35-139, 1995.

GRADING

The following weights will be considered:

Homework (individual assignment involving the computer aided solution of column generation models): 30%

Analysis of papers (individual assignment): 30%

Final exam: 40%