- Free Articles
- Reactive Scheduling of Batch Processes Encyclopedia of Optimization
- Variational methods in shape analysis Handbook of Mathematical Methods in Imaging
- History of Geomathematics: Navigation on Sea Handbook of Geomathematics
- Geomagnetic Field: Satellite Data Handbook of Geomathematics
- From Omnipotent to Omnipresent Maps Handbook of Geomathematics
**More Free Articles**

Mathematics and Statistics
>
Encyclopedia of Optimization
>
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

Keywords

See also

References

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

(1) |

*c*∊**R**^{n},*A*_{1}∊**R**^{m × n},*b*_{1}∊**R**^{m},*A*_{2}∊**R**^{q × n}and*b*_{2}∊**R**^{q}are given constants and*x*∊**R**^{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.