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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Dantzig-Wolfe Decomposition for Integer Linear Programming

  • Jacques Desrosiers,
  • Marco Lübbecke,
  • Guy Desaulniers,
  • Jean Bertrand Gauthier

摘要

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.