Dantzig–Wolfe decomposition

algorithm for solving linear programming problems with special structure

Uses your system voice; voice and rate in settings.

Q4388617Snapshot

≈ 3 min read

Names in other languages

  • cadescomposició de Dantzig-Wolfe
  • Portuguêsdecomposição de Dantzig–Wolfe
  • Portuguêsdecomposição de Dantzig–Wolfe
  • slDantzig-Wolfova dekompozicija
  • daDantzig–Wolfe-dekomposition
  • EnglishDantzig–Wolfe decomposition
  • eomalkompono de Dantzig-Wolfe
  • РусскийРазложение Данцига-Вулфа

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Dantzig–Wolfe decomposition is an algorithm for solving (mixed integer) linear programming problems by exploiting their structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 19601. Many texts on linear programming have sections dedicated to discussing this decomposition algorithm.

Dantzig–Wolfe decomposition can be used to improve the tractability of large-scale linear programs or create a tighter linear relaxation of mixed integer linear programs. & x = \sum_i \lambda_i x_i\\ & \sum_i \lambda_i = 1 \\ & x \in \mathbb{R}, ~ \lambda_i \in \mathbb{R}^+ \end{align} or equivalently \begin{align} \min ~~ & c^T \sum_i \lambda_i x_i \\ \text{subject to}~~ & A \sum_i \lambda_i x_i \leq a \\ & \sum_i \lambda_i = 1 \\ & \lambda_i \in \mathbb{R}^+ \end{align} Here the new variables \lambda_i represent the coefficient in the convex combination, and the coefficients x_i represent the points satisfying B x \leq b . In order to be exact, the formulation needs to contain one variable \lambda_i for each extreme point of the polyhedron induced by B x \leq b . This is because every point of a non-empty, bounded convex polyhedron can be represented as a convex combination of its extreme points. This leads to an intractable number of variables.

In order to be able to solve this new formulation containing an intractable number of variables, one use the column generation algorithm. This leads to an iterative algorithm where a couple (\lambda_i, x_i) is generated at every iteration.

Remarque: if the initial problem contains several constraints A x \leq a , B x \leq b , C x \leq c ... each of these constraints can be independently reformulated with the Dantzig-Wolfe method. This leads to independent sub-problems in the column generation algorithm. This fact is especially useful when the matrix constraint of the initial problem has a form of block diagonal structure.

The whole algorithm can be summarized as follows. Initialize the reformulated problem (P) with a small subset of the points x_i and their corresponding variables \lambda_i ; Find an optimal solution x^* of (P); Search for a point x_i satisfying B x \leq b whose addition to (P) may improve the value of the optimal solution x^* ; If such a point exists, add it to (P) and go to Step 2; Otherwise x^* is optimal : stop.

It can be visualized as follows.

See also

Delayed column generation Benders' decomposition

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371930466 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Dantzig–Wolfe decomposition” revision 1371930466 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL

Provenance

snapshot dantzig-wolfe-decomposition-503030-df95e52f76c5cdbd · hash df95e52f76c5cdbded8f219bb8c052181a1360c5e6e2d7655c68434731f2a6ea · captured 1787997384.0 · version history

Cite this page as: encyclopegia.org, “Dantzig–Wolfe decomposition”, snapshot dantzig-wolfe-decomposition-503030-df95e52f76c5cdbd. https://encyclopegia.org/a/dantzig-wolfe-decomposition