Dantzig-Wolfe decomposition

We consider linear programming problems of the form $$\begin{array}{rrcrcrcr}min& {{\mathbf{c}}^{(1)}}^{\mathsf{T}}{\mathbf{x}}^{(1)}& +& {{\mathbf{c}}^{(2)}}^{\mathsf{T}}{\mathbf{x}}^{(2)}& +& \cdots & +& {{\mathbf{c}}^{(k)}}^{\mathsf{T}}{\mathbf{x}}^{(k)}\\ (P)\text{s.t.}& {\mathbf{A}}^{(1)}{\mathbf{x}}^{(1)}& +& {\mathbf{A}}^{(2)}{\mathbf{x}}^{(2)}& +& \cdots & +& {\mathbf{A}}^{(k)}{\mathbf{x}}^{(k)}& =& \mathbf{b}\\ & {\mathbf{x}}^{(1)}& & & & & & & \in & P_1\\ & & & {\mathbf{x}}^{(2)}& & & & & \in & P_2\\ & & & & & \ddots & & & & ⋮\\ & & & & & & & {\mathbf{x}}^{(k)}& \in & P_k.\end{array}$$ where $\mathbf{b}\in {\mathbb{R}}^m$ for some positive integer $m$, and for $i=1,\dots ,k$, $n_i$ is a positive integer, ${\mathbf{A}}^{(i)}\in {\mathbb{R}}^{m\times n_i}$, ${\mathbf{c}}^{(i)}\in {\mathbb{R}}^{n_i}$, and $P_i$ is a pointed polyhedron.

For each $i=1,\dots ,k$, let ${\mathbf{x}}^{(i,j)}$, $j=1,\dots ,p_i$ be the extreme points of $P_i$ and let ${\mathbf{d}}^{(i,j)}$, $j=1,\dots ,r_i$ give a complete set of extreme rays of $P_i$ where $p_i$ and $r_i$ are nonnegative integers.

By Theorem 12.1, ${\mathbf{x}}^{(i)}\in P_i$ can be written as $$\sum _{j=1}^{p_i}{\lambda }_{(i,j)}{\mathbf{x}}^{(i,j)}+\sum _{j=1}^{r_i}{\gamma }_{(i,j)}{\mathbf{d}}^{(i,j)}$$ for some ${\lambda }_{(i,j)}\ge 0$, $j=1,\dots ,p_i$ and ${\gamma }_{(i,j)}\ge 0$, $j=1,\dots ,r_i$ where $\sum _{j=1}^{p_i}{\lambda }_{(i,j)}=1$.

Then $(P)$ can be reformulated as $$\begin{array}{rl}min& \sum _{i=1}^k(\sum _{j=1}^{p_i}{\hat{c}}_{(i,j)}{\lambda }_{(i,j)}+\sum _{j=1}^{r_i}{\tilde{c}}_{(i,j)}{\gamma }_{(i,j)})\\ (DW)\text{s.t.}& \sum _{i=1}^k(\sum _{j=1}^{p_i}{\lambda }_{(i,j)}{\hat{\mathbf{a}}}^{(i,j)}+\sum _{j=1}^{r_i}{\gamma }_{(i,j)}{\tilde{\mathbf{a}}}^{(i,j)})=\mathbf{b}\\ & \sum _{j=1}^{p_i}{\lambda }_{(i,j)}=1& i=1,\dots ,k,\\ & {\lambda }_{(i,j)}\ge 0& i=1,\dots ,k,j=1,\dots ,p_i,\\ & {\gamma }_{(i,j)}\ge 0& i=1,\dots ,k,j=1,\dots ,r_i.\end{array}$$ where for $i=1,\dots ,k$ we have $$\begin{array}{rl}{\hat{c}}_{(i,j)}& ={{\mathbf{c}}^{(i)}}^{\mathsf{T}}{\mathbf{x}}^{(i,j)}\\ {\hat{\mathbf{a}}}^{(i,j)}& ={\mathbf{A}}^{(i)}{\mathbf{x}}^{(i,j)}\end{array}$$ for $j=1,\dots ,p_i$, and $$\begin{array}{rl}{\tilde{c}}_{(i,j)}& ={{\mathbf{c}}^{(i)}}^{\mathsf{T}}{\mathbf{d}}^{(i,j)}\\ {\tilde{\mathbf{a}}}^{(i,j)}& ={\mathbf{A}}^{(i)}{\mathbf{d}}^{(i,j)}\end{array}$$ for $j=1,\dots ,r_i$.

Note that $(DW)$ is a linear programming problem in standard form. But it might have too many variables compared to $(P)$. To solve $(DW)$, we will use the simplex method with column generation. We illustrate the concepts on the problem $$\begin{array}{rl}min& {\mathbf{c}}^{\mathsf{T}}\mathbf{x}\\ (SP)\text{s.t.}& \mathbf{A}\mathbf{x}=\mathbf{b}\\ & \mathbf{x}\ge \mathbf{0}.\end{array}$$

Suppose that $B$ is a basis determining a basic feasible solution. Recall that the only part of $\mathbf{A}$ that is needed to compute the associated basic feasible solution is the submatrix ${\mathbf{A}}_B$. To determine if the basic feasible solution is optimal, we solve for $\mathbf{y}$ in ${\mathbf{y}}^{\mathsf{T}}{\mathbf{A}}_B={\mathbf{c}}_B^{\mathsf{T}}$ and check if it is feasible to the dual; i.e. if ${\mathbf{y}}^{\mathsf{T}}{\mathbf{A}}_j\le c_j$ for all $j\notin B$. If not, we have a $k\notin B$ such that ${\mathbf{y}}^{\mathsf{T}}{\mathbf{A}}_k>c_k$ and $x_k$ is the entering variable. The leaving variable can be obtained knowing only ${\mathbf{A}}_{B\cup \{k\}}$, ${\mathbf{c}}_{B\cup \{k\}}$, and $\mathbf{b}$. Therefore, the only step that involves knowledge of the entire $\mathbf{A}$ is in finding $k$.

In the case of $(DW)$, the check can be performed without the explicit knowledge of the entire $\mathbf{A}$. To see this, let such $\mathbf{y}$ for the dual of $(DW)$ be given by $\left[\begin{array}{c}\mathbf{u}\\ {\zeta }_1\\ ⋮\\ {\zeta }_k\end{array}\right]$. We therefore need to check for each $i\in \{1,\dots ,k\}$ if there exists $j\in \{1,\dots ,n_i\}$ such that $${\mathbf{u}}^{\mathsf{T}}{\hat{\mathbf{a}}}^{(i,j)}+{\zeta }_i>{\hat{c}}_{(i,j)}$$ or if there exists $j\in \{1,\dots ,r_i\}$ such that $${\mathbf{u}}^{\mathsf{T}}{\tilde{\mathbf{a}}}^{(i,j)}>{\tilde{c}}_{(i,j)}.$$

These inequalities can be rewritten as $${\zeta }_i>({{\mathbf{c}}^{(i)}}^{\mathsf{T}}-{\mathbf{u}}^{\mathsf{T}}{\mathbf{A}}_j^{(i)}){\mathbf{x}}^{(i,j)}$$ and $$0>({{\mathbf{c}}^{(i)}}^{\mathsf{T}}-{\mathbf{u}}^{\mathsf{T}}{\mathbf{A}}_j^{(i)}){\mathbf{d}}^{(i,j)},$$ respectively. We can handle both sets of inequalities for a particular $i\in \{1,\dots ,k\}$ by solving the subproblem $$\begin{array}{rl}min& ({{\mathbf{c}}^{(i)}}^{\mathsf{T}}-{\mathbf{u}}^{\mathsf{T}}{\mathbf{A}}_j^{(i)})\mathbf{x}\\ \text{s.t.}& \mathbf{x}\in P_i.\end{array}$$ Suppose that it has an optimal solution. By Theorem 8.7 there is one that is an extreme point ${\mathbf{x}}^{(i)}$ of $P_i$. If the optimal value is less than ${\zeta }_i$, then $${\zeta }_i>({{\mathbf{c}}^{(i)}}^{\mathsf{T}}-{\mathbf{u}}^{\mathsf{T}}{\mathbf{A}}_j^{(i)}){\mathbf{x}}^{(i)}$$ and so we have found an entering variable for $(DW)$.

Suppose that it is unbounded. By Theorem 10.5 there is an extreme ray ${\mathbf{d}}^i$ of $P_i$ so that $$0>({{\mathbf{c}}^{(i)}}^{\mathsf{T}}-{\mathbf{u}}^{\mathsf{T}}{\mathbf{A}}_j^{(i)}){\mathbf{d}}^i.$$ Again, we have found an entering variable for $(DW)$.

If none of the above applies for all $i=1,\dots ,k$, then $(DW)$ has been solved to optimality.

The computational advantage of the above method for solving $(DW)$ instead of solving $(P)$ directly is that if $k$ is large, the problem $(P)$ has many constraints. So in the case when $m$ is small and each of the subproblem is easy to solve, each iteration of the simplex method has only modest memory requirements, making it possible to solve very large instances of $(P)$.