DANTZIG-WOLFE DECOMPOSITION
Dantzig-Wolfe decomposition - The principle applied here is that the total problem consists of:
- subprograms corresponding to its almost independent parts;
- master program that ties together the subprograms.
In linear programming this applies to the following block diagonal structure, linked by master constraints.
.---------------------. | Master constraints | |_____________________| .----. | B1 | |____| .----. | B2 | |____| . . . .----. | Bk | |____|
The procedure operates on the master LP with blocks used to generate extreme points as part of the pricing .
