Revised Dantzig-Wolfe decomposition for staircase-structured linear programs
Staircase structured linear programs arise naturally in the study of engineering economic systems. One general approach to solving such LP's is the technique of nested decomposition of the primal or dual problem. The research described in this paper proposes a revised decomposition algorithm that incorporates knowledge of the structure of the staircase basis in forming the decomposed linear programs. Column proposals from the revised subproblems are shown to achieve maximum penetration against the master problem basis. The proposed algorithm resorts to the regular Dantzig-Wolfe subproblem to test for optimality. The algorithm is shown to be finite and is compared to the Abrahamson-Wittrock algorithm. Computational results indicate substantial improvement over the Dantzig- Wolfe algorithm in most cases. A numerical example of the algorithm is provided in the appendix.
- Dual nested decomposition of staircase linear programs
- A stabilized structured Dantzig-Wolfe decomposition method
- scientific article; zbMATH DE number 3856813
- scientific article; zbMATH DE number 3858842
- A Solution-Cascading Approach to the Decomposition of Staircase Linear Programs
- Dantzig-Wolfe and Lagrangian decompositions in integer linear programming
- A Forward Simplex Method for Staircase Linear Programs
- scientific article; zbMATH DE number 3856811
- A method for decomposing mixed-integer linear programs with staircase structure
- Algorithm 768: TENSOLVE
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
- A Comparative Study of Two Methods for Staircase Linear Programs
- A set of staircase linear programming test problems
- An advanced implementation of the Dantzig-Wolfe decomposition algorithm for linear programming
- Computational experience with advanced implementation of decomposition algorithms for linear programming
- Decomposition of arborescent linear programs
- Decomposition of linear programs by dynamic programming
- Decomposition Principle for Linear Programs
- Dynamic Linear Programs for Production Scheduling
- Elements of Large-Scale Mathematical Programming Part I: Concepts
- scientific article; zbMATH DE number 3856813 (Why is no real title available?)
- scientific article; zbMATH DE number 3356467 (Why is no real title available?)
- scientific article; zbMATH DE number 3371823 (Why is no real title available?)
- Nested Decomposition and Multi-Stage Linear Programs
- Nrsted decomposition for dynamic models
- Partitioning procedures for solving mixed-variables programming problems
- Solving staircase linear programs by the simplex method. I: Inversion
- Solving staircase linear programs by the simplex method. II: Pricing
- The Decomposition Algorithm for Linear Programs
- DECOMP: an implementation of Dantzig-Wolfe decomposition for linear programming
- A clustering heuristic to detect staircase structures in large scale linear programming models
- A decomposition-based approach for the multiperiod multiproduct distribution planning problem
- scientific article; zbMATH DE number 1801375 (Why is no real title available?)
- scientific article; zbMATH DE number 3856813 (Why is no real title available?)
- A method for decomposing mixed-integer linear programs with staircase structure
- A model-based approach and analysis for multi-period networks
- A stabilized structured Dantzig-Wolfe decomposition method
- Dual nested decomposition of staircase linear programs
- A dantzig-wolfe decomposition variant equivalent to basis factorization
- Decomposition of structured linear programs based on analytical centers
- Parallel processors for planning under uncertainty
- Convergence behavior of decomposition algorithms for linear programs
This page was built for publication: Revised Dantzig-Wolfe decomposition for staircase-structured linear programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3779999)