> > Decomposition Principle of Linear Programming

This is the free portion of the full article. The full article is available to licensed users only.
How do I get access?

Decomposition Principle of Linear Programming

Article Outline


See also

Keywords Optimization - Decomposition

A frequently applied approach in the history of optimization is that of decomposition, by which a large problem is decomposed into smaller problems. The principle of decomposition goes back to the seminal paper by G.B. Dantzig and P. Wolfe [2].

The basic model is a linear programming problem with two sets of constraints to be stated as follows:
where cR n , A 1R m × n , b 1R m , A 2R q × n and b 2R q are given constants and xR n is a vector of variables.
The fundamental idea is to solve (1) by interaction between two optimization problems, one of which is subject to the first set of constraints and the other subject to the second set of constraints. Denote the second set by
For simplicity we assume that X is bounded and nonempty.