Technical Report 048-2003

Title

A Primer in Column Generation

Authors

Jacques Desrosiers and Marco E. Lübbecke

Source

Download as [PDF] [ps.gz]

Classification

MSC:
primary:	90C10	Integer programming
secondary:	90-02	Research exposition
	90C05	Linear programming
	90C06	Large-scale problems
	90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut
	49M27	Decomposition methods
	65K05	Mathematical programming algorithms

Keywords

Linear Programming, Large Scale Problems, Integer Programming, Branch-and-Bound, Decomposition Methods

Abstract

We give a didactic introduction to the use of the column generation technique in linear and in particular in integer programming. We touch on both, the relevant basic theory and more advanced ideas which help in solving large scale practical problems. Our discussion includes embedding Dantzig-Wolfe decomposition and Lagrangian relaxation within a branch-and-bound framework, deriving natural branching and cutting rules by means of a so-called compact formulation, and understanding and influencing the behavior of the dual variables during column generation. Most concepts are illustrated via a small example. We close with a discussion of the classical cutting stock problem and some suggestions for further reading.