Dantzig-Wolfe Decomposition for Linear Programming

Springer eBooks, pp. 103–171

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.

Authors 4

1. Jacques Desrosiers corresponding

   HEC Montréal · Group for Research in Decision Analysis

   Affiliation as printed

   GERAD and Département de sciences de la décision, HEC Montréal, Montréal, Canada

2. Marco E. Lübbecke Aachen GERAD and School of Business and Economics

   RWTH Aachen University

   Affiliation as printed

   GERAD and School of business and economics, RWTH Aachen University, Aachen, Germany

3. Guy Desaulniers

   Polytechnique Montréal · Group for Research in Decision Analysis

   Affiliation as printed

   GERAD and Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal, Canada

4. Jean Bertrand Gauthier
   Affiliation as printed

   Mainz, Germany