Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14251
For citation please use:
Main Title: A Primer in Column Generation
Author(s): Desrosiers, Jacques
Lübbecke, Marco E.
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15478
http://dx.doi.org/10.14279/depositonce-14251
License: http://rightsstatements.org/vocab/InC/1.0/
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.
Subject(s): linear programming
large scale problems
integer programming
branch-and-bound
decomposition methods
Issue Date: 2003
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C10 Integer programming
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
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2003, 48
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-048-2003.pdf
Format: Adobe PDF | Size: 197.97 kB
DownloadShow Preview
Thumbnail
Report-048-2003.ps.gz
Format: Unknown | Size: 142.17 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.