Scholarlink

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.

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

Dantzig-Wolfe Decomposition for Linear Programming

  • 章节

  • 出版模式：

    开放获取

  • 发表日期：

    2026年

查看全文
  • Jacques Desrosiers,
  • Marco Lübbecke,
  • Guy Desaulniers,
  • Jean Bertrand Gauthier

摘要

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.