Exam (elaborations) TEST BANK FOR OPERATIONS RESEARCH Computer Science

Exam (elaborations) TEST BANK FOR OPERATIONS RESEARCH Computer Science File Intetfaces 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 CHAPTER 7 Advanced Exercises 7.1 A forestry model 7.2 A REDUCE anomaly 7.3 Assisting model management CHAPTER 8 Utilities 8.1 HPAGER 8.2 LPRENAME 8.3 FORTREF CHAPTER 9 Algorithms and Heuristics 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 CHAPTER 10 More Views 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 CHAITER 11 Rulebase Development 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 CHAITER 12 Using the Modules 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. explanations and a schema view are also illustrated. Syntactic Chapter 4 goes through some elementary exercises to demonstrate computerassisted 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. ANALYZE. .. Page 1-1 Chapter 1. Overview, Installation, and Help Man is a tool-using animal. Without tools he is nothing, with tools he is alL Thomas Carlyle This chapter is designed for a quick entry into ANALYZE. The purpose of ANALYZE is to provide computer assistance for analysis. It is presumed a linear program has already been formulated, and an instance has been generated with some language. The most common input to ANALYZE is a standard (MPS) matrix file, and we shall describe alternative input forms. Besides a matrix, ANALYZE can read solution files from a variety of solvers: MINOS, MPSIII, MPSX, OB1, and OSLo Although ANALYZE does not solve the instance of a linear program, it does provide ways to analyze the linear program and its solution. The methods we shall describe comprise three levels of use. At the very lowest level, ANALYZE provides convenient interactive query to navigate through a linear program, perhaps with a solution already obtained from some solver. A second level of use provides procedures to assist analysis in a variety of ways. Standard sensitivity questions, such as W'hat if .. ?, W'hy ... ? and W'hy not ... ?, can be answered with easy access to information about the solution. In addition, diagnostic analysis, such as when the linear program is infeasible, can be resolved efficiently. The third level provides an artificially intelligent environment with English translations of results automatically obtained. This is especially well suited for a non-expert of linear programming. The exercises in this User's Guide reinforce concepts learned in linear programming, but this is not a substitute for an introductory text. We freely use terms like dual price, basic solution, etc., which make more sense if one also has a text on linear programming to learn basic terms and concepts. After describing what you have and how to begin, an overview of the ANALYZE modular design is presented to help gain an overall appreciation for what you will use to enhance your environment for analysis. These sections are brief, but they may be skimmed. Then, in section 3, installation instructions are given for a DOS environment. You must have a 386 or 486 machine with 2mb memory. A co-processor is desirable but not necessary. Section 4 introduces some of the conventions in the interactive language of ANALYZE, such as abbreviations and some of the more popular environmental controls. Finally, the last section tells you how to obtain on-line help and further documentation. ANALYZE. .. Page 1-2 1.1 What you have and how to begin. The DOS version is on one 3~" disk (1.44mb) with the following files. File .......................................... Contents ANALDATAARC .............. Data and Documents ANALEXEC.ARC ............... Executable FLIPDOCS.ARC .................. FLIP Documents HPAGERARC .................... Pagination for HP LPRNDATAARC ............... LPRENAME Data LPRNEXEC.ARC. ............... LPRENAME Executable MOREDATA.ARC ............. More linear programs PKXARC.COM .................... ARC extraction VIEWDOCS.ARC. ............... Views Documents Codes were compiled with Lahey<R) F77L-EM/32 5.0 and linked under DOS 3.3 (the executable uses the Phar Lap extender). Begin by copying the original disks for a backup. To install ANALYZE on your IBM PS2 (or a clone) under DOS, you will need about 2mb on your hard disk (details for installation are given in § 1.3). This User's Guide is designed to be read sequentially. A reference manual may be generated by ANALYZE using EXEC DOCANAL. This and other information about on-line help is given in § 1.5. 1.2 Modular design. Figure 1-1 shows an Input/Output schematic of ANALYZE. The only required input file to ANALYZE is a matrix file. This is the (de facto) standard MPS file, which is accepted by all commercial optimizers and can be generated by most LP modeling languages (see §8.2 for a utility, called LPRENAME, that accepts another type of LP input file). For model analysis this may be sufficient, but other files are useful, such as a solution file from an optimizer. These (and other) files are described in Chapter 6. To get started, the data files (extracted from ANALDATA.ARC) contain a variety of examples, which are used in the exercises in Chapters 4, 5 and 7). Dictionaries Documents ----~ Rules I~~ other r----~ (e.g., lIS) ANALYZE. .. Page 1-3 ~ Documentation ~Sensitivity: Whatif ... ? Why ... ? Why not ... ? ANALYZE 1-----1--~Query, with multiple views ~Simplification ~ Interpretation ~ Debugging (e.g., infeasible) Figure 1-1. An Input/Output Overview of ANALYZE The functions of ANALYZE are to support analysis of results and other model management tasks. The exercises in the following chapters illustrate many kinds of analysis, starting with elementary questions of interpreting optimal solutions and debugging infeasible or anomalous results. Special procedures, such as REDUCE, are described to aid model simplification; and, a multi-view architecture aids documentation as well as on-line query. 1.3 Quick install for DOS environment. To install in a DOS environment, put the ANALYZE disk into drive a: and change directories to the path where you want to install ANALYZE. It is recommended this be an empty directory, perhaps called ANALYZE. Then, at the DOS prompt, enter: > COpy A:INSTALL.BAT [drive] Then, enter INSTALL. The default disk drive that contains ANAL YZE is a:, and you can change this by entering another drive. For example, enter INSTALL B to install from drive b (note no colon after B in the drive spec). The appropriate files will be extracted from the ARC files, and you will see a message that installation was successful. You are then ready to run ANALYZE. Once the installation is complete, you may delete INSTALL.BAT from your hard disk. Your next step is to enter ANALYZE at the DOS prompt. After some ANALYZE ... Page 1-4 sign-on information is displayed, you will be ready to test that you received everything and that all is well. After the ANALYZE prompt, enter EXEC ArnsT. You will see a lot of messages flashing over your screen. These are from the test commands being executed. After about 10 minutes (depending upon the speed of your computer), you will be prompted to continue. Simply press Enter (or Y, followed by Enter) to complete the test. At the end of the test, you should see a message that ANALYZE appears to be working, and you are left with the ANALYZE prompt. You may then continue with some exercises. To leave ANALYZE, enter QUIT. You can have a more comfortable screen if you enter COLORSCR before entering ANALYZE. This gives a blue background and yellow letters, but it might not work on your computer. If it does work, you can create a BAT file to execute COLORSCR before executing ANALYZE. If you have Microsoft Windows 3.0 or higher, you should look at ANALYZE.PIF and ANAL BAT. You might need to modify them for your environment. 1.4 Some interactive language conventions. Examples and documentation use a standard metalanguage with the following symbols (a metalanguage is a language to describe a language, in this case ANALYZE command specifications comprise the language, and their description, such as with the HELP command, uses this metalanguage, which is in fairly standard notation). All commands and keywords are upper case. Lower case words describe a type of specification. Square brackets [] enclose an optional specification. Curly braces {} enclose a list of options, one of which must be specified. An ellipsis ... denotes continued repetition of the last option. A vertical bar I denotes exclusive options. Example 1: SWITCH [name [ ••. ]] This specifies the language syntax for the SWITCH command. The outer square brackets denote that no specification need follow the SWITCH command (in which case the switches and their values are listed). If a specification does follow, it is the name of a switch (in which case the value of the switch is toggled between ON and OFF). The inner square brackets with the ellipsis means that additional switch names can be specified. The following illustrates the possibilities. ANALYZE. .. Page 1-5 SWITCH .. .lists switches and their settings SWITCH ECHO ... changes value of switch named ECHO SWITCH ECHO ERROR ... changes values of two switches, named ECHO and ERROR Example 2: DISPLAY [ROWICOL [conditional]] [f/options] This specifies the language syntax for the DISPlAY command. The square brackets denote options, so a valid specification is just DISPlA Y with no other specification. The vertical bar that separates keywords ROWand COL means that the following specifications are valid. DISPLAY ROW DISPLAY COL The [condi t i ana 1] means another optional specification, which is a "conditional" (to be defined later) can follow the ROW or COL specification. Independent of whether the ROW or COL option is specified, there is another option indicated by [f / opt i on s]. The double slash (j I) is necessary to precede the options that can be specified. The following are valid specifications (whose meanings will be defined later). DISPLAY ROW //LEVEL DISPLAY COL * //LEVEL DISPLAY //LEVEL Example 3: SOLUTION {MINOS lOBI I OSL I XMP I MPS} [filespec] This specifies the language syntax for the SOLUTION command. The Curly braces indicate that one of the options must be specified, and the vertical bars indicate that exactly one must be specified. The square brackets indicate that the file specification (filespec) is optional. This means the following specifications are valid. SOLUTION MINOS SOLUTION OBI SOLUTION OSL SOLUTION XMP SOLUTION MPS SOLUTION MINOS MYFILE ANALYZE. .. Page 1-6 In all but the last case, a file is not specified. In the last case, the file is specified as MYFILE. Example 4: SCHEMA [DISPLAY [options] I CLEARI {LOAD I SAVE} [filespec]] This specifies the language for the SCHEMA command. The outer square brackets mean that just SCHEMA can be specified with no further specification (as before, the meaning is described later; here only the metalanguage is illustrated). What follows means the following are valid. SCHEMA DISPLAY [options] SCHEMA CLEAR SCHEMA LOAD [filespec] SCHEMA SAVE [filespec] Note the use of the curly braces for the LOAD and SAVE specifications following SCHEMA. Whichever of those are specified, a filespec (file specification) is optional. There are also options following DISPLAY, and the square brackets state that SCHEMA DISPLAY is a valid specification without options. As we go through the exercises in subsequent chapters, you will experience some conventions about the interactive language (FLIP). One is that you must WCK CAPS, because the interactive command language is case-sensitive, and all commands and keywords use capital letters.