Dantzig-Wolfe Decomposition for Linear Programming

Springer eBooks 2026 Book chapter Open access

Read full text
Authors: Jacques Desrosiers, Marco E. Lübbecke, Guy Desaulniers, Jean Bertrand Gauthier
DOI: 10.1007/978-3-031-96917-1_3
Cited by: 0

Abstract

Abstract This chapter describes the Dantzig-Wolfe decomposition principle applied to linear programming. This decomposition principle is no more and no less than a mathematical reformulation which uses the Minkowski-Weyl theorem to express some constraints under an alternative geometric interpretation. As the resulting reformulation typically contains a huge number of variables, we carry the essence of the column generation algorithm by deriving the master and pricing problems. We then oppose the given linear program to its reformulation and finally explore different examples.

Fields of Study & Subjects

Advanced Optimization Algorithms Research Optimization and Mathematical Programming Complexity and Algorithms in Graphs

Publication details

Journal / source
Springer eBooks
Pages
103–171
Publication date
1 January 2026
Language
EN
Document type
Book chapter