Dantzig-Wolfe decomposition

From Glossary

Jump to: navigation, search

The principle applied here is that the total problem consists of:

  1. subprograms corresponding to its almost independent parts;
  2. 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.

Views
Personal tools