A Primer in Column Generation
| dc.contributor.author | Desrosiers, Jacques | |
| dc.contributor.author | Lübbecke, Marco E. | |
| dc.date.accessioned | 2021-12-17T10:05:22Z | |
| dc.date.available | 2021-12-17T10:05:22Z | |
| dc.date.issued | 2003 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15478 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14251 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | linear programming | en |
| dc.subject.other | large scale problems | en |
| dc.subject.other | integer programming | en |
| dc.subject.other | branch-and-bound | en |
| dc.subject.other | decomposition methods | en |
| dc.title | A Primer in Column Generation | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2003, 48 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90C10 Integer programming | en |
| tub.subject.msc2000 | 90-02 Research exposition | en |
| tub.subject.msc2000 | 90C05 Linear programming | en |
| tub.subject.msc2000 | 90C06 Large-scale problems | en |
| tub.subject.msc2000 | 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut | en |
| tub.subject.msc2000 | 49M27 Decomposition methods | en |
| tub.subject.msc2000 | 65K05 Mathematical programming algorithms | en |