 |
       |
 |
|
|
|
|
The Library component of IBM Optimization Solutions and Library family of products is a suite of subroutines for manipulating the models and solving the
resulting minimization problems of mathematical optimization. The Library comprises an extensive collection of software building blocks from which a
knowledgeable practitioner can create a customized optimization application. These building blocks can be combined with other code to develop solutions to
optimization problems (such as nonlinear problems) that are beyond the capabilities of the current Solutions components. The Parallel Extensions and Stochastic
Extensions products are, as their names imply, add-ons to the Library that provide extensions to its capabilities. The Parallel
Extensions product adds parallel processing capabilities, that can be used to develop new parallel applications or to parallelize (without modification)
existing serial Optimization Library applications. The Stochastic Extensions product adds an entire suite of new modules that extend the
capabilities of the Library to stochastic programming problems.
Brief Description
The modules of the Library, and of its extensions, are written primarily in portable C, with a few assembler language routines to enhance performance. Included are routines in the following categories:
| Parallel Capabilities |
The Parallel Extensions product provides parallel versions of the interior point (LP and QP), MIP, and decomposition solver modules, marked above by a double asterisk. |
The Library's input/output modules can handle MPS and Lotus 1-2-3 files. Alternatively, you can input data in any format, or generate it as needed, and then pass it to library modules in internal arrays. It is even possible to use Library modules to combine input data from different sources. The Library and the Stochastic Extensions are available for numerous platforms, from PC's to mainframes, including UNIX based workstations from IBM, Hewlett Packard, SGI, and Sun. (On December 4, 1998, the Parallel Extensions will be available for AIX platforms. Availability for other platforms will follow.)
Library modules are competitive in speed with other commercial optimization software, and faster than most. However, their most noteworthy strong points
are versatility and robustness. The solvers have special strategies for dealing with degeneracies and numerical instabilities. The MIP solver is capable of
handling either a linear or quadratic objective function with linear constraints. The MIP solver can be instructed to use the primal or dual simplex (or simplex
based) solver on the LP (or QP) relaxations. Over a hundred control variables and nine
user exit subroutines are provided to make it easy to monitor and modify tactics as the solution progresses.
Control Variables
The user settable control variables enable comprehensive control of the execution of library modules. These multi-position switches permit setting, among
many other things: the number of simplex iterations to be done with one pricing strategy before changing to another, the tolerances for detecting zero values
and certain error conditions, the allowed amounts of primal and dual infeasibilities, the initial weight for the feasibility component of the composite
objective function used by the simplex method solver, the rate at which the barrier parameter of the interior point solvers is reduced, the maximum number of
steps of the simplex method to be done before the matrix of basis vectors is refactored, and the maximum number of nodes allowed in the branch and bound tree
for the MIP solver. Additional information on control variables is presented throughout this document. You may consult the overview of
control variables, Index Control Variables, Integer Control
Variables, Character and Real Control Variables, or finally Appendix C. Control Variables.
User Exits
Embedded calls in each solver, and in the message handler, to user exit
subroutines make possible extensive customization of applications. To take
advantage of these requires writing one or more subroutines to replace
stubs distributed with the Library, and compiling and loading them with
the main program. At load time, the replacement routines will supersede
the corresponding stubs, and at run time they will gain control in the
midst of the execution of the subroutines. Users are thus empowered with
the means to monitor and control execution of the modules while they are
running. For example, one could simply write out intermediate information
as the solution progressed, or change solution tactics in a major way in
the midst of a computation. For additional information on user exits, see
"Understanding User Exit Subroutines."
Related Information
A collection of rudimentary sample application programs, in both C and FORTRAN, is distributed with the Library, so
that application development need not necessarily "start from scratch." A source of information on model building and problem solving using Library modules is
the book "Optimization with IBM OSL," by Hung, Rom, and Waren (ISBN 0-89426-244-0), published by Scientific Press, which is now a subsidiary of
Duxbury Press. URLs for sources of additional information on OSL and on optimization in general can be found in
Links.
Descriptions of the solver modules
For LP problems, the Library includes both primal and dual versions of the justly famous simplex method developed by George
Dantzig, of Stanford University. The simplex algorithm performs an efficient, systematic search for an optimal solution among the vertices on the boundary
of the feasible region. The simplex method is the most commonly used method for solving linear programming problems. In the variants implemented in the
Library, the work is not divided into two phases. A composite objective function is used throughout, so that variables are simultaneously moved toward an
optimum as feasibility is approached. As previously mentioned, the simplex solvers have a special strategy for circumventing degeneracies, and they permit
adjusting the pricing strategy to enhance performance.
An interior-point solver searches for an optimal solution in the interior of the feasible region while working toward the boundary. The interior point LP/QP
solver included in the Library uses a logarithmic barrier method in which a sequence of functions, each a linear objective function augmented by a sum of
logarithmic terms multiplied by a barrier parameter, is minimized. The algorithm used is a primal/dual method with a predictor corrector scheme. This algorithm
can be used to solve regularized LP, or QP, problems in which a small quadratic perturbation has been added to the objective. For LP problems, the Library
interior point solver provides an option to switch over to a simplex solver, at (or near) completion of the interior point iterations, to obtain a basic
feasible solution.
Network programming problems are linear programming problems that optimize the transmission of resources through a network of possible routes. The pure
network solver implemented in the Library uses a variant of the simplex method that has been modified to take advantage of the graphical nature of the problems
and the simple form of the constraint matrices. This solver runs up to fifty times as fast as an unmodified simplex solver for pure network problems. The solver
recognizes shortest path and maximum flow problems, and solves these with a special algorithm. A composite objective function is used, and thus problem
variables move toward optimal values as feasibility is approached. As before, the pricing strategy may be adjusted to improve performance.
The Library includes two QP solvers capable of minimizing a convex quadratic objective function subject to linear constraints. One solver uses a two-stage
simplex based algorithm, and the other uses an interior point algorithm applied
to a regularized form of the problem. Since the optimum may occur in the interior of the feasible region, the simplex method alone cannot be used to solve QP
problems. In its first stage, the simplex based algorithm solves a sequence of approximating LP problems and related very simple QP problems until successive
approximations are "close enough" together. In its second stage, this solver analyzes the QP problem directly, using an extension of the simplex method that
permits a quadratic objective function and converges very rapidly when given a good starting value.
Mixed-integer programming (MIP) problems are problems in which some of the variables are constrained to take on only integer values. Decision variables,
whose values determine which of two alternatives is to be implemented (such as whether to build a plant or to produce a particular product), are often modeled
as 0/1 integer variables. For MIP problems, the Library includes a branch and bound solver that can handle either a linear or quadratic objective function with
linear constraints. Low level control of the branching strategy is provided via user exits. The (primal or dual) simplex LP
solver may be used on LP relaxations, and the (primal or dual) simplex based QP solver may be used on QP relaxations. For linear MIP problems, an
optional preprocessor can probe on 0/1 variables, successively fixing variable values first to zero and then to one, and
then investigating the logical consequences of these assignments. The result is similar to branching, but the analysis does not require solving the LP
subproblems. The preprocessor builds implication lists for use throughout the solution process. The preprocessor may detect infeasibility, fix variables,
modify or add constraints, or even identify an optimum. Other MIP processing modules can transform general integer problems
into binary integer problems (and back), and can identify special ordered sets in input data.
Downloadable documentation
If you would like to have the html files that contain the Library User's Guide, click here to download the zipped HTML files
(756 KB). If you prefer to have a hard copy of the documentation, click here to download either a postscript (HUGE -
8928KB) or zipped postscript (BIG - 1753KB) version.
| Notes: |
|
     |