Decomposition Methods for Mathematical Programming

Philippe Mahey

ABSTRACT

Decomposition methods are mainly used to solve iteratively large-scale optimization problems that present a structure of interrelated subsystems. Reducing dimension is not the only motivation; other important aspects are partitioning heterogeneous problems, decentralizing local decisions, and parallelizing computations among different processors. We review here the classical decomposition techniques in mathematical programming among which are price- and resource-directive schemes. Duality as well as column or row generation play a fundamental role, and we complete the exposition with regularization techniques based on symmetric duality, which leads to primal-dual schemes acting like separable augmented Lagrangian algorithms.