
5
Dantzig-Wolfe Decomposition
5.1 Introduction
In this chapter, we consider methods for solving linear programs that exhibit
special structure. In particular, we consider linear programs that are in block
angular form and develop the Dantzig-Wolfe decomposition method for solving
such problems. Economic interpretations of the decomposition are discussed.
5.2 Decomposition for Block Angular Linear Programs
Consider a linear program of the form
minimize c
T
x
subject to Ax ≤ b
x ≥ 0,
and where A is an m × n matrix, and suppose that the constraint matrix is
of the form
A =
L
1
L
2
··· L
K
A
1
A
2
.
.
.
.
.
.
A
K
,
where L
k
is a submatrix with dimension m
L
× n
k
for