Large-Scale Linear Programming

During the week of June 2-6, 1980, the System and Decision Sciences Area of the International Institute for Applied Systems Analysis organized a workshop on large-scale linear programming in collaboration with the Systems Optimization Laboratory (SOL) of Stanford University, and co-sponsored by the Mathematical Programming Society (MPS). The participants in the meeting were invited from amongst those who actively contribute to research in large-scale linear programming methodology (including development of algorithms and software). The first volume of the Proceedings contains five chapters. The first is an historical review by George B. Dantzig of his own and related research in time-staged linear programming problems. Chapter 2 contains five papers which address various techniques for exploiting sparsity and degeneracy in the now standard LU decomposition of the basis used with the simplex algorithm for standard (unstructured) problems. The six papers of Chapter 3 concern aspects of variants of the simplex method which take into account through basis factorization the specific block-angular structure of constraint matrices generated by dynamic and/or stochastic linear programs. In Chapter 4, five papers address extensions of the original Dantzig-Wolfe procedure for utilizing the structure of planning problems by decomposing the original LP into LP subproblems coordinated by a relatively simple LP master problem of a certain type. Chapter 5 contains four papers which constitute a mini-symposium on the now famous Shor-Khachian ellipsoidal method applied to both real and integer linear programs. The first chapter of Volume 2 contains three papers on non-simplex methods for linear programming. The remaining chapters of Volume 2 concern topics of present interest in the field. A bibliography a large-scale linear programming research completes Volume 2