Dantzig–Wolfe decomposition

Short description: Algorithm for solving linear programming problems with special structure

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 1960. 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.

Explanation using column generation

The Dantzig-Wolfe decomposition considers the following initial linear program.

$\begin{array}{rl}\min & c^{T}x\\ \text{subject to}& Ax\le a\\ & Bx\le b\\ & x\in \mathbb{ℝ}\end{array}$

The decomposition starts by reformulating the problem. the constraint $Bx\le b$ is equivalently reformulating by writing $x$ as a convex combination of points satisfying $Bx\le b$. This leads to the following linear program.

$\begin{array}{rl}\min & c^{T}x\\ \text{subject to}& Ax\le a\\ & x=\sum _i{\lambda }_i{x}_i\\ & \sum _i{\lambda }_i=1\\ & x\in \mathbb{ℝ},{\lambda }_i\in {\mathbb{ℝ}}^{+}\end{array}$or equivalently $\begin{array}{rl}\min & c^T\sum _i{\lambda }_i{x}_i\\ \text{subject to}& A\sum _i{\lambda }_i{x}_i\le a\\ & \sum _i{\lambda }_i=1\\ & {\lambda }_i\in {\mathbb{ℝ}}^{+}\end{array}$

Here the new variables ${\lambda }_i$ represent the coefficient in the convex combination, and the coefficients $x_i$represent the points satisfying $Bx\le b$. In order to be exact, the formulation needs to contain one variable ${\lambda }_i$ for each extreme point of the polyhedron induced by $Bx\le 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 $Ax\le a$, $Bx\le b$, $Cx\le 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.

1. Initialize the reformulated problem (P) with a small subset of the points $x_i$ and their corresponding variables ${\lambda }_i$;
2. Find an optimal solution $x^{*}$of (P);
3. Search for a point $x_i$ satisfying $Bx\le b$ whose addition to (P) may improve the value of the optimal solution $x^{*}$;
4. If such a point exists, add it to (P) and go to Step 2;
5. Otherwise $x^{*}$is optimal : stop.

It can be visualized as follows.

Initialization of (P) with a small subset of the points $x_i$ (red polyhedron). Black arrow : objective function c; gray poly : $Ax\le a$; dashed blue poly : $Bx\le b$.	Iteration 1. A direction (red arrow) in which to search a new point $x_i$ is created with the dual variables of (P). The farthest point in this direction satisfying $Bx\le b$ is found and added to (P).
Iteration 2. Re-optimization over (P). Then, the farthest point in the dual direction satisfying $Bx\le b$ is found and added to (P).	The algorithm keeps going until no more improving points can be found.

Exploiting special structure

The main use case for the Dantzig–Wolfe decomposition is when the constraint matrix of the linear program has the following 'almost diagonal' structure visualized below.

File:DW Block Angular Matrix.jpg

Here, the set of constraints D is usually be identified as "connecting", "coupling", or "complicating" constraints. Meanwhile each constraint block $F_i$ is going to be reformulated using the Dantig-Wolfe method. This leads to one sub-problem for each block $F_i$.

The two main reasons why the Dantzig-Wolfe method works especially well in this case are the following. First, each block $F_i$ only applies to a subset of the variables. This means the corresponding sub-problem will be a lot smaller than the original problem (less constraints and less variables) which means it can be solved faster. Second, although the sub-problem can always be solved independently, in the case of a diagonal structure the sub-problems are usually less linked. Indeed, suppose that $F_1$ and $F_2$ share a variable $x_1$, then they have to 'agree' on the value of $x_1$. This means every time the $F_1$ sub-problem proposes a new point with a different value for $x_1$, the $F_2$ sub-problem also has to generate a new point with an agreeing value for $x_1$. This slows down the overall process.

Implementation

There are examples of the implementation of Dantzig–Wolfe decomposition available in the closed source AMPL and GAMS mathematical modeling software. There are general, parallel, and fast implementations available as open-source software, including some provided by JuMP and the GNU Linear Programming Kit.

The algorithm can be implemented such that the subproblems are solved in parallel, since their solutions are completely independent. When this is the case, there are options for the master program as to how the columns should be integrated into the master. The master may wait until each subproblem has completed and then incorporate all columns that improve the objective or it may choose a smaller subset of those columns. Another option is that the master may take only the first available column and then stop and restart all of the subproblems with new objectives based upon the incorporation of the newest column.

Another design choice for implementation involves columns that exit the basis at each iteration of the algorithm. Those columns may be retained, immediately discarded, or discarded via some policy after future iterations (for example, remove all non-basic columns every 10 iterations).

A (2001) computational evaluation of Dantzig-Wolfe in general and Dantzig-Wolfe and parallel computation is the PhD thesis by J. R. Tebboth

See also

• Delayed column generation
• Benders' decomposition