Horizontal mixed decomposition

DOI10.1016/S0377-2217(86)80004-2MaRDI QIDQ581228zbMATH OpenFDO

Authors Bert R. Meijboom

Publication date 1986

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0377-2217(86)80004-2

zbMATH Keywords

block- angular linear programmingdecompositionLagrangian dualitymixed use of prices and budgettangential approximationtwo-level organization

Mathematics Subject Classification ID

Decomposition methods (49M27) Numerical mathematical programming methods (65K05) Operations research and management science (90B99) Linear programming (90C05) Large-scale problems in mathematical programming (90C06) Applications of mathematical programming (90C90)

Review text

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.

Recommendations

• Homogeneous bivariate decompositions
• Horizontal Composability Revisited
• A modified decomposition
• Horizontal Principal Structure of Layered Mixed Matrices: Decomposition of Discrete Systems by Design-Variable Selections
• scientific article; zbMATH DE number 617925
• Decomposition integrals
• The decomposition method and distributions
• Proper generalized decomposition
• scientific article; zbMATH DE number 4049169

Cites work

• A note on mixed procedures for decomposing linear programming problems
• Convergence Conditions for Nonlinear Programming Algorithms
• scientific article; zbMATH DE number 3819432 (Why is no real title available?)
• scientific article; zbMATH DE number 3356467 (Why is no real title available?)
• Primal Resource-Directive Approaches for Optimizing Nonlinear Decomposable Systems

Cited in

(2)

• A framework for collaborative planning and state-of-the-art
• Multilevel decomposition in mixed-integer block programming

This page was built for publication: Horizontal mixed decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581228)