Using the IBM Optimization Subroutine Library at UIC Document #2729012 And a List of OSL Routines February 11, 1991 =============================================================================== Introduction Brief Overview of Solution Optimization Mathematical programming techniques can be applied to problems where you want to minimize or maximize a function, subject to a set of constraints. A solu- tion is said to be feasible if it satisfies the constraints. A solution is said to be optimal if it yields the smallest or largest value of the objective function among all feasible solutions. The IBM OSL library routines allow you to find the optimal solutions to several types of problems using linear pro- gramming, mixed-integer programming and quadratic programming. They are avail- able on the CMS system at UIC but not on MVS. Linear Programming: Two linear programming methods are offered by OSL: a sim- plex method, which includes a primal and dual algorithm, and an interior- point barrier method. The simplex method is the most common method for solving linear programming problems. A simplex algorithm searches for the optimal solution among the vertices of the feasible polyhedron, as opposed to an interior-point barrier method, which searches for solutions by start- ing in the interior and working toward the boundary of the feasible polyhe- dron. OSL gives the user the option of selecting the method to be used in the solution of the problem. Mixed-integer Programming: Mixed-integer programmings problems are linear pro- gramming problems where some of the variables are constrained to be inte- gers. For example, a mixed-integer programming problem may be concerned with the number of esats on an airplane or airplanes on a route. Decision variables, such as whether to produce a particular product, are oten modeled by 0-1 integer variables. Mixed-integer programming problems are solved by solving as a series of linear programming problems. Quadratic Programming: Quadratic programming problems solved by OSL have a convex quadratic objective function and linear constraints. There is also a subroutine for solving parametric quadratic problems. The Optimization Subroutine Library The IBM Optimization Subroutine Library (OSL) is a collection of high- performance mathematical subroutines for use by programs that solve optimiza- tion problems. OSL can be used with VS FORTRAN, PL/1 and C/370 programs to solve several types of mathematical programming problems using linear, mixed- integer and quadratic programming methods. OSL takes advantage of the Vector Facility of the IBM 3090 whenever possible to improve performance. OSL con- sists of two types of subroutines: * High-level routines which allow users to solve a problem without requiring them to have a detailed knowledge of mathematical programming. Using the IBM OSL Library at UIC page 2 =============================================================================== * Low-level routines which allow users with detailed knowledge to structure algorithms without having to write their programs from scratch. Using the OSL on CMS To use the OSL on UICVM CMS at UIC, you must first attach the disk with the library using the command: GETDISK OSL You must then inform the operating system that the OSL text and macro libraries should be searched for routines. * For the macro library, enter: GLOBAL MACLIB EKKINCF * For the text library, you have a choice. = If you are using the OSL library with for VS FORTRAN, C/370 or PL/1, you can use the standard CMS GLOBAL TXTLIB command. Enter: GLOBAL TXTLIB EKKLIB VFORTLIB other_libs were "other libs" are ALL of the other TXTLIBs that your program _ ___ requires, such as the ESSL or IMSL libraries, if you use them. = Or, only when you are using VS FORTRAN, you can use the TXTLIB option of the UIC FORTVCLG and FORTVLG execs; enter: FORTVCLG pgmname (TXTLIB EKKLIB other_options where "pgmname" is the filename of the CMS file containing your FORTRAN program, and "other_options" are other options of the FORTVCLG exec. This method automatically includes the VS FORTRAN, ESSL and IMSL libraries. The method of actually calling the OSL routines follows the normal subroutine calling procedures of the language you are using, so you can use any procedures you currently use for compiling programs. However, there is one additional thing you must do before you load your program: you must increase the loader table space. Do this by entering: SET LDRTBLS 10 before you load your compiled program. If you are using the FORTVxxx execs, the loading step is indicated by the "L", as in FORTVCLG. This is the CMS SET _ command that you are using here; for more information, enter: HELP CMS SET Further Information The IBM OSL Guide and Reference contains a great deal of information to help potential users of OSL understand the concepts of mathematical programming and to formulate their problems in ways that the OSL can help solve. It includes discussions of strategies for solving mathematical programming problems, OSL data structures, Mathematical Programming System (MPS) format, OSL utilities, Using the IBM OSL Library at UIC page 3 =============================================================================== advice on debugging programs which use OSL, a complete description of each of the OSL subroutines and 23 sample programs to show how OSL can be used in dif- ferent situations. Copies of the IBM OSL Guide and Reference are available in the Computer Center reference documentation racks (in Room 2249F SEL, Room B001 BSB and Room 105 BGRC). List of Routines in OSL All OSL routine names begin with the letters EKK: Subroutine: Description: EKKBASI Read a starting basis from a file in MPS fixed format EKKBASO Write the current basis to a file in MPS fixed format EKKBCDO Write a model to a file in MPS fixed format EKKBSLV Solve a linear programming problem using the interior-point barrier method EKKCGET Request current values of character control variables EKKCOL Add, replace, get or delete a column in the problem matrix EKKCOPY Create a matrix stored by columns or by rows EKKCRSH Crash; produce a starting basis EKKCSET Set character control variables EKKDSCA Describe mathematical programming application EKKDSCB Describe one block of a model matrix EKKDSCM Describe a mathematical programming model EKKGEMV Compute a matrix vector product EKKGES Solve a basic system of equations EKKGTMD Get a model from a file EKKGTMI Get model information EKKHIS Reserve permanent space for user arrays EKKIGET Request current values of integer control variables EKKINIT Initialize OSL EKKINVT Invert; create the primal and dual solution corresponding to a giv- en basis EKKISET Set integer control variables EKKLMDL Specify a linear model EKKMPS Read an MPS input file EKKMSAV Save the option settings for a message EKKMSET Set new option settings for a message EKKMSLV Solve a mixed-integer programming problem EKKMSTR Restore the saved option settings for a message EKKNGET Request current start indicies of OSL information EKKNLBS Create a basis of all logical variables EKKNWMT Create a new copy of a matrix EKKPOPS Pop; restore storage information EKKPRSL Presolve; reduce the problem size EKKPRTS Print the problem solution EKKPSHS Push; Save current storage information EKKPSSL Postsolve; map the solution back to original variables EKKPTMD Put a model into a file EKKPTMI Put current model information EKKQMDL Specify a quadratic model EKKQMPS Read a quadratic matrix from a file in MPS EKKQPAR Solve a parametrix family quadratic programming problem Using the IBM OSL Library at UIC page 4 =============================================================================== EKKQSLV Solve a quadratic programming problem EKKRGET Request current values of real control variables EKKROW Add, replace or delete a row in the problem matrix EKKRSET Set real control variables EKKSCAL Scale the coefficient matrix EKKSMAP Print the storage map EKKSSLV Solve a linear programming problem using the simplex method EKKSTAT Print problem statistics User Exit Subroutines: Subroutine: Description: EKKBRNU Branch user exit subroutine EKKCHNU Choose node user exit subroutine EKKEVNU Evaluate a node user exit subroutine EKKITRU Iteration user exit subroutine EKKMSGU Message user exit subroutine