DECOMP: an Implementation of Dantzig-Wolfe Decomposition for Linear ProgrammingFor linear optimization models that can be formulated as linear programs with the block-angular structure, i.e. independent subproblems with coupling constraints, the Dantzig-Wolfe decomposition principle provides an elegant framework of solution algorithms as well as economic interpretation. This monograph is the complete documentation of DECOMP: a robust implementation of the Dantzig-Wolfe decomposition method in FORTRAN. The code can serve as a very convenient starting point for further investigation, both computational and economic, of parallelism in large-scale systems. It can also be used as supplemental material in a second course in linear programming, computational mathematical programming, or large-scale systems. |
Contents
1 | |
PROGRAM SUBROUTINES | 33 |
PORTABILITY ISSUES | 168 |
END OF SORT ROUTINE PUT OUT BELOW BUMPETAS PART OFU | 172 |
IF LR3 GE LR4 LR LR4 | 178 |
MREGJK | 184 |
IF DABSALL 1 LE ZTOLZE GO TO 2000 | 191 |
203 | |
Other editions - View all
Common terms and phrases
basic BTRAN CALL FORMC candidate column CHUZR compute cost vector coupling rows current cycle D-W Phase Dantzig-Wolfe decomposition data array DECOMP default Dimension direct access file DSUM dual vector elementary matrix entering column entering the basis eta file eta vector extreme point extreme ray feasible FTRAN Gaussian elimination INDATA indicates infeasible input INVERT STATISTICS IPROS IROWP ITCOUNT STATUS ith row KFASE KMULT KSTR KVEC linear programming lines LMAX LMAXP1 logical LSUB major cycle master problem matrix MAXCA proposals Maximum number MAXIMUM ROW ERROR MPS format MSTAT multiple pricing NCAND NCASUB NCOL NETA NELEM non-zero elements NONZ O ETAS NPROS NROW NROWO number of columns Number of coupling number of proposals Number of rows Number of subproblems objective value optimality output pivot row proposal buffer reduced cost rhs columns secondary storage selected for multiple STRUCTURAL COLUMNS Subroutine unbounded unboundedness update VALUE VECIN YA(I zero