Horizontal mixed decomposition (Q581228)

The usual classification of decomposition algorithms for block-angular linear programming problems is based on the distinction between distribution of common resources by prices or by direct allocations. In this paper a new decomposition method is proposed in which a part of the common constraints is coordinated by prices and the other part by direct allocations. The mixed use of prices and budget is more realistic for the planning procedure in real-world organizations. Using the Lagrangian duality theory the dual problem of the original block-angular linear programming problem is formulated and then tangential approximation is applied to derive relaxed versions of the primal and dual problem. The algorithm approximates the solution of the primal and of the dual problem by solving their relaxed versions, and adding new constraints to the relaxed problems when necessary. This procedure simultaneously generates a decreasing sequence of upper bounds as well as an increasing sequence of lower bounds for the optimal solution value. Without much extra effort, globally feasible solutions with improving value can be computed. The contribution of the present paper consists in the correct mathematical foundation of mixed coordination by prices and budgets in a two-level organization.