338 Lecture Notes in Economics and Mathematical Systems James K. Ho · Rangaraja P. Sundarraj DECOMP: an Implementation of Dantzig-Wolfe Decomposition for Linear Programming Lectu re Notes in Economics and Mathematical Systems Managing Editors: M. Beckmann and W. Krelle 338 James K. Ho R. P. Sundarraj DECOMP: an Implementation of Dantzig-Wolfe Decomposition for Linear Programming Springer Science+Business Media, LLC Editorial Board H. Albach M. Beckmann (Managing Editor) P.Dhrymes G. Fandei G. Feichtinger J. Green W. Hildenbrand W. Krelle (Managing Editor) H. P. Künzi K. Ritter R. Sato U. Schittko P. Schönfeld R. Selten Managing Editors Prof. Or. M. Beckmann Brown University Providence, RI 02912, USA Prof. Or. W. Krelle Institut für Gesellschafts- und Wirtschaftswissenschaften der Universität Bonn Adenauerallee 24-42, 0-5300 Bonn, FRG Authors Professor James K. Ho College of Business Administration, Management Science Program The University ofTennessee Knoxville, TN 37996-0562, USA Professor Rangaraja P. Sundarraj Graduate School of Management Clark University Worcester, MA 01610-1477, USA ISBN 978-0-387-97154-4 ISBN 978-1-4684-9397-9 (eBook) DOI 10.1007/978-1-4684-9397-9 IS concernea, speclTIcallY tne ngnts 01 translation, repnntmg, re-use 01 Illustrations, recltatlon, broadcasting, reproduction on microfilms or in other ways, and storage in data banks. Duplication of this publication or parts thereof is only permitted under the provisions of the German Copyright Law of September 9, 1965, in its version of June 24, 1985, and a copyright fee must always be paid. Violations fall under the prosecution act of the German Copyright Law. © Springer Science+Business Media New York 1989 Original1y published by Springer-Verlag New York, Inc., in 1989. 2847/3140-543210 - Printed on acid-free paper Preface The decomposition approach to solving large, complex problems plays an important role in exploiting parallel computation made possible by the latest development in computer architecture. The orignal problem is divided into a number of smaller, independent subproblems whose solutions, when suitably coordinated, produce the desired result. The \ coordinating procedure is usually iterative in nature. At each iteration, the independent subproblems can be solved concurrently on parallel processors. Apart from computational efficiency, this approach has significant interpretation as a model for the competitive equilibrium of decentralized systems. Since in reality, information among components of a system is processed concurrently, decomposition methods using parallel computation can provide insight into the dynamics of such interaction. For linear optimization models that can be formulated as linear pro grams 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 econornic interpretation. This monograph is the compIete documentation of DECOMP: a robust implementation of the Dantzig-Wolfe decomposition method in FORTRAN. The code can serve a:; a very convenient starting point for further investigation, both computational and econornic, of parallelism in large-scale systems. It can also be used as supplemental material in a second course in linear programming, computational mathematical programrning, or large scale systems. The code had evolved over aperiod of more than fifteen years. Many researchers played significant roles in its development, the foremost being John Tomlin, Carlos Winkler, Etienne Loute and Benoit Culot. Funding for related projects that helped sustained DECOMP had been provided by the Department of Energy, the Office of Naval Research, the European Economic Community, and the Belgian Ministry of Scientific Policy. The preparation of this monograph is partially supported by the Office ofNaval Research under Grant NOO014-89-J-1528. The entire text and all ilustrations were prepared by the authors using MacWrite and MacDraw on Apple Macintosh computers with an AppIe Laser printer. J. K. H. R. P. S. Knoxville, June 1989 Table of Contents CHAPTERI IN1RODUcrrON 1.1 Overview 1 1.2 Scope and Purpose 3 1.3 Availability ofthe DECOMP Code 4 CHAPTER 2 SPECIFICATIONS FOR A ROBUST CODE 2.1 The Revised Simplex Method 5 2.2 Specifications for a Robust Implementation of RSM 6 2.3 Pseudo-Code for RSM 11 2.4 Numerical Example of RSM 13 2.5 Dantzig-Wolfe Decomposition 19 2.6 Specifications for a Robust D-W Code 26 2.7 Pseudo-Code for DECOMP 30 CHAPTER 3 PROGRAM SUBROUTINES 3.1 Subroutine BTRAN 33 3.2 Subroutine CHANGE 36 3.3 Subroutine CHECK 39 3.4 Subroutine CHSOL 49 3.5 Subroutine CHUZR 53 3.6 Subroutine FORMC 61 3.7 Subroutine FTRAN 66 3.8 Subroutine INDA T A 73 3.9 Subroutine INPUT 83 3.10 Subroutine INVERT 91 3.11 Subroutine ITEROP 110 3.12 Subroutine MASTER 112 3.13 Subroutine NORMAL 120 3.14 Subroutine PACK 131 3.15 Subroutine POLICY 141 3.16 Subroutine PRICE 145 3.17 Subroutine RESULT 149 VI 3.18 Subroutine UNP ACK 157 3.19 Subroutine UNRAV L 158 3.20 Subroutine UPBETA 163 3.21 Subroutine VECfOR 164 3.22 Subroutine WRETA 165 CHAPTER 4 PORTABILITY ISSUES 4.1 Direct Access Device 168 4.2 NAMELIST Statements 170 CHAPTER5 USER'S GUIDE 5.1 Dimension of Arrays 172 5.2 InputData 173 5.3 OutputData 175 5.4 An Example 179 5.5 Variable Dictionary 196 BIBLIOGRAPHY 203 INDEX 205 CHAPTERI Introduction J, 1. Qyervjew DECOMP is a Fortran code of the Dantzig-Wolfe (D-W) decomposition algotithm for solving block-angular linear programs. Originally coded in 1973 by Carlos Winkler at the Systems Optirnization Laboratory (SOL) at Stanford University, DECOMP was built around John Tomlin's LPM1 (Tomlin [1973]), an all-in-core implementation of the revised simplex method. Since then James Ho and his European collaborators, notably Etienne Loute at the Center for Operations Research and Econometrics in Belgium, had expanded and improved upon the code as well as adapting it to run on various machines, including IBM's 370 series, CDC's Cyber series and DATA General's MV8000. It was the prototype for subsequent implementations based on commercial software (e.g. DECOMPSX with IBM's MPSX/370 in Ho & Loute [1981]) that provided significant benchmark results in LP decomposition (Ho & Loute [1983]). More recently, R,P. Sundarraj adapted the code for DEC's VAX computers in both the UNIX and VMS environment. DECOMP, as documented herein, is dimensioned to solve problems with up to 4000 rows, 10,000 columns and 55,000 non-zero elements and is intended primarily to be an experimental tool for research on computational aspects of large scale linear programrning. Also, it has proven to be robust and relatively portable and may actually be useful for routine applications in certain computing environments. Since its introduction by George Dantzig and Philip Wolfe in 1960, the decomposition approach to large, structured linear pro grams has only met with lirnited success in practical applications. Early attempts indicated that convergence may be poor. Later on, because of tremendous advances in sparse matrix techniques for the revised simplex method, it became even more difficult to compete directly with commercial LP software. This is especially true on problems that can be routinely processed by the latter. For an overview of the historical development in an updated perspective, the reader is referred to Ho [1987]. One major feature of decomposition is the decoupling of the subproblems. This independence of the component problems lends itself naturally to parallel processing. However, it is only recently, with the advent of multi-processor computers, that the potential advantages of D-W decomposition algorithms can be empirically explored. Initial results are 2 very promising. In Ho et al [1988], an implementation known as DECOMPAR was described. It ran on an experimental multicomputer, the CRYSTAL system (Dewitt et al [1987]) which consisted of twenty VAX 11nSO minicomputers connected in a token ring architecture at the University of Wisconsin at Madison. This software tool was effective in several research projects before the CRYSTAL system became obsolete and went out of commission. One of the projects involved the demonstration of parallel decomposition applied to planning models in electric power generation (EPRI [1989]). Test cases were derived from electric generation dispatch, which seeks to operate a collection of generating units to meet power demands under various technological and regulatory constraints; and in multiregicinal electric generation expansion, which selects regional capacity expansions that allow the system to meet demands through inter-regional power exchange. Parallel decomposition was shown to be a viable approach. Another project led to new insights into the dynamics of information in distributed decision systems (Ho & Lee [1989]). In the interpretation of D-W decomposition (See Dantzig [1963], Burton & Obel [1977], [1980], Dirickx & Jennergren [1979]) as the decentralized coordination of coupled, semi-autonomous subsystems, the effect of timing of communication among the agents had heretofore not been closely examined. In an effort to explain the performance of DECOMP AR on various classes of problems, the concept of information schemes was developed and their dynamics were shown to playamajor role in the behavior of the system. The relatively short life span of an experimental system such as CRYSTAL is actually witness to the rapidity with which commercial multicomputer technology matures and penetrates the market. By 1988, no less than a dozen machines, of both distributed and shared memory architecture are available and becoming increasingly cost-effective. An implemen tation of D-W decomposition known as DECUBE has recently been completed for an Intel iPSC/2-d6, a hypercube computer with 64 processors (Ho & Gnanendran [198~]). It is shown that material requirements planning LP's (Ho & McKenney [1988]) with 30,000 constraints can be solved in about ten minutes. Previously, such performance would require a mainframe computer costing at least twenty times as much. Both DECOMPAR and DECUBE are based on the serial code DECOMP. With the continuing trend in parallel computing with multiple processors (see e.g. Hillis [1987]), there is no doubt that significant interest and further research in LP decomposition will be renewed. As robust experimental codes for large-scale optimization are non-trivial to assemble, DECOMP can be used as a powerful building block. While this code went through many stages of development, there has never been a comprehensive documentation. This mono graph presents a detailed documentation of DECOMP and serves as a programmer's guide to both its design and coding. 3 1.2. SCQpe and Purpose DECOMP is not a commercial production code. However, in order to become an effective and robust experimental tool, it has evolved into a rather sophisticated and complex pro gram. Our purpose is to incorporate as much tutorial material as appropriate into an otherwise purely technical documentation. Most readers will only be interested in how such a code works. For them, Chapter 2 reviews the D-W decomposition principle as well as specifications for an efficient implementation. A pseudo-code for the algorithm is also presented. The brief description of the major subroutines in Chapter 3 may also be of interest. Actual users of the code will need the user's guide in Chapter 5. It includes instructions to prepare the input data, and interpretation of the output data. A complete run of a small example problem is also given. Serious students of the implementation of aLP decomposition code and programmers who need to modify, adapt or extend the code are referred to the detailed comments in Chapter 3, the portability issues in Chapter 4 and the dictionary of variables in Chapter 5. In should be remarked that the underlying LP solver in DECOMP is an efficient all-in-core revised simplex code for sparse linear programs based on J. Tomlin's LPMl (Tomlin [1973]). The heart of this solver is a pre-assigned pivot scheme for the L-U factorization of the basis matrix. Although general treatments can be found in modern LP textbooks (e.g. Murtagh [1981], Chvatal [1983]), details of such implementation are scarce in the literature. The documentation of the revised simplex (FORMC, BTRAN, PRICE, FTRAN, CHUZR, etc), and basis factorization (INVERT) subroutines in Chapter 3 can therefore also serve to fill this gap. The original Dantzig-Wolfe decomposition principle (Dantzig & Wolfe [1960]) provides a general framework for an entire class of convergent algorithms. For experimental purposes, many strategie options are built into DECOMP. These tend to complicate any effort to explain the code because of the multitude of cases that arise. For this reason, the reader should keep in mind that substantial cross referencing may be necessary to track down certain fine points and that it is impossible to provide (at least not in a linear text) a comprehensive guide to all paths of significant interest. With knowledge of the decomposition method in Chapter 2, the reader can use the pseudo code for DECOMP at the end of that chapter as the "big picture" and progress ively fill in details from Chapter 3 as warranted by individual interest. While DECOMP is a fully functional code that has proved to be robust for a diverse collection of test problems, there may still be remaining programming errors or flaws in the logical design. Also, no specific effort has gone into cleaning up the code in terms of program ming style and conventions. 4 1.3 AyailabiIity or tbe DECOMP Code DECOMP is in the public domain and has been distributed to a number of researchers worldwide over the years. It is available on a diskette subject to a nominal material and handling fee. Inquiries should be addressed to Professor J.K. Ho, Management Science Program, University of Tennessee, Knoxville, TN 37996, USA.