Dantzig-Wolfe Decomposition for Integer Linear Programming

Springer eBooks, pp. 173–293

Abstract

Abstract This chapter extends the Dantzig-Wolfe decomposition principle to integer linear programs. Indeed, we capitalize on the fact that we can request partial integrality requirements of the compact formulation in the pricing problem. We investigate two related, but different approaches in deriving the integer master and integer pricing problems. The first is based on the convexification of the reformulated domain, as in the classical Dantzig-Wolfe decomposition for linear programming. The second is based on its discretization, taking into account also interior points of the reformulated domain. In the context of integer linear programming, both of these provide more than only mathematical reformulations. In particular, we show that solving the linear relaxation of the integer master problem may provide a better bound than that of the compact formulation.

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