direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2003

A Primer in Column Generation
Zitatschlüssel Report-048-2003
Autor Jacques Desrosiers and Marco E. L\übbecke
Jahr 2003
Nummer 048
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag