This part of the book is organized into three chapters providing guidance and information on how to use the Optimization Library:
This section gives you an overview of:
The Optimization Library is a suite of subroutines for manipulating the models and solving the resulting minimization or maximization problems of mathematical optimization. The subroutines are written primarily in portable C, with a few assembler language routines to enhance performance. The Optimization Library includes routines in nine categories:
The library's input/output modules can handle MPS and Lotus 1-2-3 files. Alternatively, data may be input in any format, or generated as needed, and passed to library modules in internal arrays. The library is available for numerous platforms, from PC's to mainframes, including UNIX based workstations from IBM, Hewlett Packard, SGI, and Sun.
High-level subroutines with default control paths provide you with powerful problem solving capabilities, without your needing a detailed knowledge of mathematical programming. At the same time, Library subroutines have numerous parameters, control variables, and user exits that make it easy to develop customized solution strategies without having to write detailed solver programs. This means that the Optimization Library is ideal for production use in making business decisions, and also for research use in developing new techniques.
Flexibility is also evident in the variety of operating systems supported by the Optimization Library.
Optimization Library applications developed for one environment can run in another, without significant changes. They can meet your optimization needs whether you have a PC, workstation, or mainframe, or even a network of some (or all) of these.
Mathematical optimization is concerned with finding an optimal allocation of limited resources by choosing an alternative that maximizes payoff, or minimizes cost, from among the many that satisfy the limiting constraints. A solution is just a set of values of the problem variables that satisfy the bounds on the variables. A solution is said to be feasible if it also satisfies the constraints of the problem. A solution is said to be optimal if it yields the optimum (largest or smallest, as the case may be) value of the objective function among all feasible solutions. The Optimization Library provides the tools that allow you to find optimal solutions to linear programming, mixed-integer programming, and quadratic programming problems.
The Optimization Library offers simplex, interior-point, and pure network methods for LP problems. The simplex solvers provide both primal and dual algorithms; all have special strategies for dealing with degeneracies. The interior-point solvers use primal and primal-dual barrier methods. The pure network solver uses a version of the simplex method that takes special advantage of the form of network constraint matrices.
The simplex method is the most commonly used method for solving linear programming problems. A simplex algorithm searches for an optimal solution among the vertices of the feasible region, as opposed to an interior-point method, which searches for solutions by starting in the interior and working toward the boundary of the feasible region.
The Optimization Library includes a facility for pure network optimization. Many common linear programming problems, such as task assignment, scheduling, and vehicle routing can be expressed as pure network problems. The underlying structure of these problems permits solution by a simplified simplex method, providing significant improvement in computational efficiency.
The Optimization Library provides LP sensitivity analysis and LP parametrics that can be used to analyze the effects of changes in the model assumptions on the solution. Sensitivity analysis allows you to determine, for each variable, the maximum range of costs that maintain the optimal basis. For each row and variable, maximum ranges to maintain upper and lower bounds for the optimal basis are determined. Parametrics allows you to investigate changes in groups of variables and rows simultaneously. Costs and bounds are allowed to range over specified intervals. Both sensitivity analysis and parametrics save you time and increase flexibility, because a range of alternatives can be considered on one call to an Optimization Library subroutine.
The Optimization Library provides LP infeasibility analysis. Infeasibility analysis can be used to identify shortcomings in model formulation. Options include identifying:
Mixed-integer programming problems are optimization problems in which some of the variables are constrained to be integers. For example, a mixed-integer programming problem may be concerned with the number of seats on an airplane or airplanes on a route. Decision variables, such as whether to produce a particular product, are often modeled by 0-1 integer variables.
For MIP problems (with either linear or quadratic objective function), the library includes both a branch and bound solver and an optional preprocessor that probes on the 0-1 variables. Low level control of the branching strategy is provided via user exits. In the preprocessor probing, zero/one variables are successively fixed, first to zero and then to one, and the logical consequences of these assignments are investigated. The result is similar to branching, but the analysis does not require solving the LP relaxations. The preprocessor may detect infeasibility, fix variables, modify or add constraints, or even identify an optimum.
Quadratic programming problems are optimization problems for which the objective function is quadratic in the problem variables. The QP solver uses a fast, robust two stage algorithm to minimize a quadratic objective function with a positive semidefinite quadratic coefficient matrix subject to linear constraints. Since the optimum may occur in the interior of the feasible region, the simplex method alone cannot be used to solve QP problems. The first subalgorithm solves an approximating LP problem, and a related very simple QP problem at each iteration. When successive approximations are close enough together, the second subalgorithm is used. This extension of the simplex method permits a quadratic objective function, and converges very rapidly when given a good starting value. The Library also includes a subroutine for solving parametric quadratic problems.
Before you begin using the subroutines, you should spend some time reading "Application Design Principles". This part contains information about mathematical programming that is specific to using Optimization Library modules. The first chapter in this part, "OSL Terms and Concepts", will give you a basic understanding of the terminology and concepts. The rest of the chapters tell you how this information relates to all the subroutines.
The Optimization Library has an easy-to-use application programming interface. Your Optimization Library application program is portable across the different operating environments, provided that you have complied with the restrictions for the environments. Although coding changes are not required, of course your program will have to be recompiled.
The Optimization Library can be used in a workstation environment, running on IBM RISC System/6000, Hewlett-Packard PA RISC 9000, Silicon Graphics, and Sun and SPARCstations; IBM compatible personal computers using the Pentium** processor. These operating systems are listed in material viewable on our WWW web page.
Notes:
Direct access storage is required for the Optimization Library, and is defined during host product installation. The Optimization Library Program Directory specifies these storage requirements for host operating platforms. For workstation requirements, see the appropriate Memo to Users and README file.
During program processing, Optimization Library also uses storage in your program region for its subroutines and for work space, and it may use direct access storage. See "Storage Allocation" and the subroutine EKKDSCA (Describe a Mathematical Programming Application) for information on how storage is organized and used.
[ Top of Page | Previous Page | Next Page | Table of Contents ]