A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions: A User's Guide for ANALYZE(c) OPERATIONS RESEARCH/COMPUTER SCIENCE INTERFACE SERIES Ramesh Sharda, Editor ConocolDuPont Chair of Management of Technology Professor of Management Science & Information Systems College of Business Administration Oklahoma State University Stillwater, Oklahoma, U.S.A. A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions: A User's Guide for ANALYZE<c> J. IIARVEY GREENBERG Mathematics Department, Campus Box 170 University of Colorado at Denver P. 0. Box 173364 Denver, CO 80217-3364 BITNET: hgreenberg@cudenver ' ' ~· Springer-Science+Business Media, LLC (c)This User's Guide and ANALYZE software are protected by U.S. copyright laws. Ubrary of Congress Cataloglng·in-Publlcation Data Greenberg, Harvey J. A computer·assisted analysis system for mathematical programming models and solutions : a user's guide for ANALYZE I Harvey J. Greenberg. p. cm. •• (Operations research/computer science interface series) "September 1992." lncludes index. Additional material to this book can be downloaded from http://extras.springer.com. ISBN 978-1-4613-6428-3 ISBN 978-1-4615-3248-1 (eBook) DOI 10.1007/978-1-4615-3248-1 1. ünear programming --Data processing. 2. ANALYZE. I. Title. II. Series. T57.74.G727 1993 519.7'2--dc20 92-43505 aP Copyright C 1993 Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 1993 Softcoverreprint ofthe bardeover 1st edition 1993 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, mechanical, photo-copying, recording, or otherwise, without the prior written permission of the publisber, Springer Science+Business Media, LLC. Printed on acid-free paper. ANALYZE. .. Page v Acknowledgements I wish to thank our industrial sponsors - Amoco Oil Company, IBM, Shell Development Company, Chesapeake Decision Sciences, Ketron Management Science, GAMS Development Corporation, MathPro, Inc., and Maximal Software - for their support, including their participation in the project, itself. Earlier support was also provided by General Research Corporation and US West. Milton M. Gutterman (formerly with Amoco) provided code and testing for the TSO and SUN environments; and, Jon Jacobs (formerly with GRC), Thomas Dehne (Ketron) and David Heltne (Shell) provided code and testing for the CMS environment. Optimizers were provided by Roy Marsten (OBI) and Michael Saunders (MINOS). Support for MINOS was provided by John Stone (Ketron). John Chinneck provided code for determining an irreducible infeasible subsystem (lIS). I wish to thank colleagues on the research team - John Chinneck, Fred Glover, Weldon Lodwick, Gautam Mitra and Frederic Murphy. A special thanks goes to COlleagues and students who critically reviewed earlier drafts of this User's Guide and whose comments have led to this clearer version. They are: JOHN CHINNECK, Carleton University ERIC DRAVNIEKS, Carleton University ROBBIN GILFORD, University of Colorado at Denver MILTON M. GlJTI'ERMAN, Amoco Oil Company CHARLES HALSEY, University of Colorado at Denver WELDON LoDWICK, University of Colorado at Denver FREDERIcH. MURPHY, Temple University Last, but not least, an earlier version of this work was partially supported by the Office of Naval Research (contract #N-00014-88-K-OI04). ANALYZE. .. Page vii Contents INTRODUCTION CHAPTER 1 OvelView, Installation, and Help 1.1 What you have and how to begin 1.2 Modular design 1.3 Quick install for DOS environment 1.4 Some interactive language conventions 1.5 On-line documentation 2 Anatomy of a Linear Program CHAPTER 2.1 Algebraicform 2.2 Model Syntax 2.3 Conditional delineation of rows and columns 3 Simple Queries CHAPTER 3.1 The sign-on and interactive conventions 3.2 Basic query commands 3.3 Syntax-based explanations 3.4 Schema view 4 Examples ofA nalysis CHAPTER 4.1 Price interpretation for the LP expert 4.2 Automatic interpretation 4.3 A case of infeasibility 4.4 A case of unboundedness 5 Further Examples CHAPTER 5.1 Blocking 5.2 Rates of substitution 5.3 Using the basis 5.4 The REDUCE command 5.5 The AGGREGAT command ANALYZE. .. Page viii 6 File Intetfaces CHAPTER 6.1 Environment controls 6.2 Dictionaries, documents, help and keyword files 6.3 Execution files 6.4 Matrix and packed files 6.5 Solution files 6.6 Syntax files 6.7 Rule files 6.8 Submatrix, block, schema and graph files 6.9 Setting up an environment for analysis 7 Advanced Exercises CHAPTER 7.1 A forestry model 7.2 A REDUCE anomaly 7.3 Assisting model management 8 Utilities CHAPTER 8.1 HPAGER 8.2 LPRENAME 8.3 FORTREF 9 Algorithms and Heuristics CHAPTER 9.1 Discourse formation 9.2 Path tracing 9.3 Basis rearrangement 9.4 Rates of substitution 9.5 Redundancy test 9.6 Successive bound reduction 9.7 Logical implication tests 10 More Views CHAPTER 10.1 Block plots 10.2 Step plots 10.3 Table formations and displays 10.4 Graphs of linear programs 10.5 Schema equations ANALYZE. .. Page ix 11 Rulebase Development CHAITER 11.1 Basic concepts and tools 11.2 Rule file commands 11.3 Simple examples 11.4 Price interpretation 11.5 Testing new rule files 12 Using the Modules CHAITER 12.1 Setup for an alternative computing environment 12.2 FLIP 12.3 GETMAT 12.4 VIEWS Appendix A: Error Messages Appendix B: The ANALYZE Library Index ANALYZE. .. Page xi Introduction Welcome to ANALYZE, designed to provide computer assistance for analyzing linear programs and their solutions. Chapter 1 gives an overview of ANALYZE and how to install it. It also describes how to get started and how to obtain further documentation and help on-line. Chapter 2 reviews the forms of linear programming models and describes the syntax of a model. One of the routine, but important, functions of ANALYZE is to enable convenient access to rows and columns in the matrix by conditional delineation. Chapter 3 illustrates simple queries, like DISPLAY, LIST, and PICTURE. This chapter also introduces the SUBMAT command level to define any submatrix by an arbitrary sequence of additions, deletions and reversals. Syntactic explanations and a schema view are also illustrated. Chapter 4 goes through some elementary exercises to demonstrate computer assisted analysis and introduce additional conventions of the ANALYZE language. Besides simple queries, it demonstrates the INTERPRT command, which automates the analysis process and gives English explanations of results. The last 2 exercises are diagnoses of elementary infeasible instances of a particular model. Chapter 5 progresses to some advanced uses of ANALYZE. The first is blocking to obtain macro views of the model and for finding embedded substructures, like a netform. The second is showing rates of substitution described by the basic equations. Then, the use of the REDUCE and BASIS commands are illustrated for a variety of applications, including solution analysis, infeasibility diagnosis, and redundancy detection. Chapter 6 describes environment controls, such as the use of the SETUP command. It proceeds to explain the use of various file types that provide interfaces with other systems and to offer additional computer-assisted analysis to model users. This includes the use of dictionaries, documents, execution macros, syntax files and rule files. Chapter 7 goes through some advanced exercises. These involve more subtle uses of ANALYZE, and some practical limitations are given. It concludes with describing how ANALYZE can assist model management. Chapter 8 describes the utilities. Of particular importance is the ability to rename rows and columns with the LPRENAME system. This allows longer than 8- character names, a limit imposed by the standard matrix file, and this provides an interface with modeling systems like GAMS, AMPL and MIMI. ANALYZE. .. Page xii Chapter 9 presents some features of the fundamental algorithms and heuristics in ANALYZE. The purpose is to enhance awareness of the meaning of the results obtained by these procedures. Chapter 10 describes more views of a linear program. The first two are graphic plots. The first of these is an option with the BLOCK command; the second is an option with the SHOW command. The third additional view is a table that can be formed from the syntax and displayed in rectangular format with the TABLE command. Finally, schema equations are illustrated as an algebraic view of the underlying model, taken from the schema table. These views are not in the standard version of ANALYZE (see Chapter 1 on installation). Chapter 11 extends the brief discussion of rule files, given in chapter 6, to a full presentation of what capabilities are available and how to use them. After basic terms and concepts, examples are presented from rule files that come with ANALYZE to support the INTERPRT command, which is illustrated in early chapters. Chapter 12 applies only if you received source code (contact the author for information about availability). It explains how you can use the modules used by ANALYZE for designing your own system or changing some of the algorithms. Knowledge of FORTRAN/77 is assumed. Appendix A gives guidance to error messages, and Appendix B describes the extended library of linear programs and how to get more information about them with suggestions for additional exercises. Advice from a student Although this User's Guide is self-contained, knowledge of linear programming is assumed. The exercises in the chapters show how to use ANALYZE to retrieve information, sometimes with complex procedures, but it does not explicitly teach what information to obtain. This User's Guide is designed for people who already use linear programming, and for students who are learning linear programming. In the latter case, ANALYZE serves to support an LP laboratory, corequisite with lectures, and the exercises need classroom discussion to guide the students.