A Primer in Column Generation

dc.contributor.authorDesrosiers, Jacques
dc.contributor.authorLübbecke, Marco E.
dc.date.accessioned2021-12-17T10:05:22Z
dc.date.available2021-12-17T10:05:22Z
dc.date.issued2003
dc.description.abstractWe 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.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15478
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14251
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherlinear programmingen
dc.subject.otherlarge scale problemsen
dc.subject.otherinteger programmingen
dc.subject.otherbranch-and-bounden
dc.subject.otherdecomposition methodsen
dc.titleA Primer in Column Generationen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften>Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2003, 48en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090C10 Integer programmingen
tub.subject.msc200090-02 Research expositionen
tub.subject.msc200090C05 Linear programmingen
tub.subject.msc200090C06 Large-scale problemsen
tub.subject.msc200090C57 Polyhedral combinatorics, branch-and-bound, branch-and-cuten
tub.subject.msc200049M27 Decomposition methodsen
tub.subject.msc200065K05 Mathematical programming algorithmsen
Files
Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-048-2003.pdf
Size:
197.97 KB
Format:
Adobe Portable Document Format
Description:
Loading…
Thumbnail Image
Name:
Report-048-2003.ps.gz
Size:
142.17 KB
Format:
Unknown data format
Description:
Collections