DECOMP: an implementation of Dantzig-Wolfe decomposition for linear programming (Q1187721)

Consider the problem ``Minimize \(\sum c_ rx_ r\) subject to \(\sum A_{0r}x_ r=b_ 0\), \(A_{1r}x_ r=b_ r\), \(r=1,2,...,R\); \(x\geq 0''\). Here, there are R sets of independent constraints that are tied together by the first constraint set. Dantzig and Wolfe (D-W) gave a decomposition technique for obtaining the optimal solution by solving the R subproblems involving the independent constraints and a corresponding master problem that makes use of the fact that the optimal solution is a convex combination of the extreme points of the subproblems. As stated by the authors, ``Since its introduction in 1960, the decomposition algorithm to large, structured linear programs has only met with limited success in practical applications. Because of tremendous advances in sparse matrix techniques, it became difficult (for the (D-W) decomposition technique) to compete with commercial LP software''. However, ``the independence of the component problems lends itself naturally to parallel processing. With the advent of multi-processor computers, the potential advantage of the D-W algorithm can be empirically explored.'' This monograph is the complete documentation of DECOMP: a robust implementation of the Dantzig Wolfe decomposition method in FORTRAN. After a short introduction in Chapter 1, Chapter 2 begins by a review of the revised simplex method. This is followed by some of the underlying theory behind the D-W decomposition technique. The chapter concludes with a pseudo-code for DECOMP describing how the various subroutines are put together to make up the algorithm. Chapter 3, which is the heart of the book, gives the detailed codes for the various subroutines. Although the program is written in FORTRAN and hence easily portable, some parts involving input-output are machine dependent. These parts are identified and discussed in Chapter 4. Chapter 5 is entitled ``User's Guide'' and gives instructions for someone wanting to implement DECOMP. The chapter concludes with a numerical example. In their introduction, the authors caution the reader with the statement ``While DECOMP is a fully functional code there may still be remaining errors and flaws in the logical design. Also, no specific effort has gone into cleaning up the code in terms of programming style and conventions''. Despite these reservations, the book and its code should prove to be helpful to anyone wanting to use the D-W algorithm on very large suitably structured problems.