Reprinted from the

Department of Industrial Engineering and Management Sciences

Northwestern University, Evanston, IL 60208-3119

`4er@iems.nwu.edu -
http://iems.nwu.edu/~4er/`

This article offers a different kind of "buyer's guide" to
optimization software. It is intended as a complement to lists of
products and vendors, and in fact mentions no products by name. It is
instead organized according to the questions that any potential
purchaser of this software ought to ask. Part
1 was directed toward relatively general market concerns:

- What optimization problems does the product address?
- What aspects of optimization modeling does the product address?
- What aspects of optimization modeling does the vendor address?

- How are optimization problems expressed?
- How are problems solved?
- How are results viewed and analyzed?
- What help is provided for diagnosing errors?
- What help is provided for model management?

The most practical way to express large-scale optimization
problems to computers is by specifying them in two parts: a symbolic
*model* and explicit *data*. A symbolic description of a
model is easy to recognize by its use of *index sets* to concisely
describe collections of similar model components, as well as summations
and other iterated operations. Explicit data values typically appear
as lists of factories, products, planning periods, and the like, and as
tables of numerical values such as factory-product capacities, product
demands, and factory-warehouse shipping costs per period. Optimization
systems employing this approach can be categorized according to the
formats that they require you to use in writing the model and data.
The choice between these formats is often one of the most important
factors in deciding between rival optimization packages, as no one
representation has proven to be the best for all situations.

Considering first the model, the most varied group of
representations are *declarative:* they describe the components
of the model without specifying how the description is to be translated
(along with the data) into input for the solver. *Text-based*
representations describe a model through a series of statements in a
specially designed computer language, typed into a file using any text
editor. Common varieties include:

*Algebraic*(or row-wise): using a language based on common mathematical notation, including the familiar operators for addition, multiplication, and so forth, and the e summation terminology. Constraints are written as equations and inequalities in the decision variables.*Activity-oriented*(or column-wise): defining activities, modeled by decision variables, through a specification of their inputs and outputs of materials and products.*Block-schematic:*characterizing the variables and constraints through descriptions of the nonzero blocks of coefficients in the constraint matrix.

*Netform-based:*using standard representations of nodes and arcs to describe networks on which optimization problems can be posed. The modeling system can address a variety of built-in problem types, including problems of optimal flow, optimal path identification, and optimal network design.*Application-specific:*using a graphical representation defined for a specific class of problems.

An opposite approach is taken by systems that employ a
*procedural* description of models. They require that you write
an executable computer program, either in a programming language
specialized for optimization, or in a general-purpose programming
language for which functions or object classes have been supplied.
Indexed collections of variables and constraints are defined by writing
loops.

Systems based on procedural descriptions have tended to fall
out of favor in recent years, because they require a substantial degree
of translation from the modeler's original conception, and are prone to
inherent difficulties of debugging and maintenance [1]. Instead the focus of development has moved
toward hybrid systems that can provide powerful and flexible procedural
statements while encouraging a fundamentally declarative style of model
description. A number of algebraic modeling languages have been
augmented with looping and conditional statements that are used to
manipulate data and results and to implement iterative schemes that
solve a series of optimization problems. General-purpose
object-oriented programming languages also have a much more declarative
nature than traditional programming languages. A C++ class library,
for example, can overload arithmetic operators (such as `+` and
`*`) so that they take operands and return results of type
"expression"; similarly overloaded relational operators (such as
`=` and `<=`) return results of type "constraint" that
are automatically passed to routines that generate input for solvers.

Turning to the data, many systems support their own text-based tabular input formats, which have been specialized to handle the multidimensional sets and data tables that are common in mathematical programming applications. Many also offer the alternative of retrieving data from standard database and spreadsheet packages. Several systems take advantage of straightforward correspondences that can be established between the descriptions of data in algebraic modeling languages and the tables of a relational database [2]. A correspondence between optimization data and conventional two-dimensional spreadsheets is also possible but is harder to define, unless the spreadsheet's contents are simply treated as relational database tables.

With respect to both power of expression and ease of use, the appropriateness of the above alternatives can vary greatly from one application to the next. Developers' descriptions of the "power" and "convenience" of their systems can only begin to tell you which modeling language or graphical interface will best meet the needs of your situation. You may have to experiment with competing packages -- perhaps by using each to build a scaled-down test model -- before you can appreciate the implications of their differences in your circumstances.

You may come across a few rules of thumb for determining whether a particular solver is likely to be superior for your application. Some nonlinear solvers are considered to be best for larger, "mostly linear" problems, for example, while others excel on smaller, "highly nonlinear" ones. Rules of this kind provide only the roughest sort of indicator, however. To reliably choose one solver over others, your decision has to be based on actual computational experience -- yours or others' -- with realistic applications. It is easiest to look for speed of solution, of course, but indications of reliability are also important. For problems that have many alternative optimal solutions, the nature of the solution may also be a concern; simplex algorithms for linear programming tend to return a solution in which a lot of the variables are at their bounds, for instance, whereas interior point algorithms tend to return a solution from the "center" of the optimal set.

In the preceding general discussion, it has been convenient to treat "solver" and "algorithm" as being more or less synonymous. In reality a solver is often a package of algorithms, sold in various configurations (at various prices). Each algorithm moreover recognizes a variety of parameters that have the potential to influence performance considerably. All parameters have "default" settings that have been chosen to provide good performance on average, but other settings are made available because they have proven to be significantly superior in tests on some problems. Benchmarks based only on the defaults can be seriously mistaken, particularly for integer and nonlinear problems, and for linear programs that require a number of iterations much greater than the number of constraints.

The entire business of selecting a solver varies greatly in importance. For a considerable proportion of applications, the difficulty of formulating a correct model and gathering data greatly outweighs the difficulty of solving any resulting optimization problems. Even where the problems are hard to solve, the choice of solver may depend as much on how you formulate your model as on any algorithmic advantages. In the hardest cases, usually involving integer or nonlinear variables, formulation and algorithm selection are carried out together as part of a broader process seeking some way to get useful solutions to a problem.

Indeed, a common mistake is to assume that a solver appropriate to your application must already exist. If you can express your problem in a standard mathematical form such as a linear program, then you are justified in assuming that a suitable solver can be found. If you have a problem that doesn't seem to fit into the categories addressed by any of the solvers you can find, however, then software purchases alone are not going to help; you need to break your problem into smaller and more tractable ones, or to back off to a simpler problem, or to enlist some help in designing a new algorithm. This circumstance occurs most commonly in situations that involve complex discrete or combinatorial decisions. Less frequently, the only natural formulations for a problem have too many variables or constraints to be handled by current computers or software.

Even though broad classes of optimization problems remain too large or too hard to solve, however, the range of problems that can be solved at reasonable cost is much greater today than even 5 or 10 years ago, thanks to advances in computers, mathematics, and software design. The most important advances have only begun to appear in textbooks, and are only partially described even in the technical literature. This is another reason to choose a solver based on benchmarking of actual software.

To support building and testing models, you need to be able to select and examine results in a variety of ways that cannot be predicted in advance. A questionable value for the objective may lead you to look at the values of certain collections of variables, which may in turn suggest that you examine all of the nonzero slacks in certain constraints involving those variables. Further investigation may involve other associated values such as dual prices and reduced costs. At this stage, you need a flexible mechanism that displays results quickly and interactively. Such a mechanism can be based on interactive commands, or on a graphical interface of lists and dialogues.

To support regular use of models, you need to be able to specify well-formatted displays of the results. Since the same displays will be used over many runs of a model, a somewhat more cumbersome but more powerful interface is acceptable. In a two-dimensional table, for example, you want to be able to meaningfully label the rows and columns, to control the precision of numbers so that the columns line up, to treat very small values as zeroes and to suppress zeroes in various ways. Some optimization systems let you specify format strings like those used in C or Fortran. Systems that provide a specialized programming language (as discussed previously) can provide very precise control over displays by making a formatted "print" statement available for use within loops and tests. Because programs for displaying results produce output that is meant for people to read, they are not as hard to debug and maintain as programs for generating problem instances.

Whether for prototyping or production use, an optimization system must do more than simply display result values returned by the solver. The sheer size of large-scale optimization problems, in which tens of thousands of variables are not unusual, dictates that the "raw" results be boiled down into more comprehensible summary statistics. Often the values of greatest interest are computed from a combination of data and variable values. The best way to judge the effect of capacity constraints, for example, may be to display the percentage of capacity used, which is a function of capacity constants and of linear expressions in the variables representing capacity use. The most attractive way of providing this flexibility is by allowing for the display of expressions in the data and variables. Systems based on algebraic modeling languages may have an advantage in this respect, as they already support a powerful variety of expressions for the purpose of specifying models.

Besides being numerous, the results of an optimization run are often multiply indexed. Systems vary in their abilities to specify which indices vary along the rows of a table, which along the columns, and which define "slices" in data of more than two dimensions.

All systems provide for some form of text output, and some provide graphical output as well. Some also provide for output in a form usable by other popular software, notably database management systems and spreadsheet packages; this other software provides sophisticated data manipulation and reporting tools that are already familiar to many optimization users.

For systems that offer a specialized procedural language, it would be desirable to have a debugging tool comparable to symbolic debuggers for general-purpose programming languages. Although current optimization systems are not nearly so sophisticated, some do provide a mode for stepping one statement at a time through a program.

The debugging facilities in solvers mainly consist of messages warning you of exceptional conditions such as unboundedness and infeasibility. Some do offer connections to additional algorithmic routines, however, that can locate and highlight infeasible, trivial or redundant constraint structures.

Versions are most likely to proliferate when a model is being
developed, or in the course of a strategic modeling exercise that by
nature requires frequent changes. Much the same considerations apply
to different versions (or *cases* or *scenarios*) of data. A
few optimization systems can maintain for you a list, or better yet a
*tree,* of versions together with comments, solutions, and other
information that is hard to summarize in only a file name. In addition
to displaying the tree of versions in informative ways, these systems
may provide convenient features for displaying the differences between
versions and for creating a new node of the tree by modifying the
version at some existing node. To save storage space, only the
differences between adjacent instances in the tree may be recorded.
Building on this feature, a system may allow models to define an
optimum over a number of scenarios that occur with certain
probabilities; the resulting *stochastic programming* or *robust
optimization* problems tend to yield more realistic results for
planning applications.

Model management features of another kind are needed to support grand iterative schemes based on decomposition, column generation, relaxation, and similar principles. In systems that provide a modeling language with programming features (as discussed previously), iterative schemes can be implemented by defining two or more different models that are solved in alternation; after an instance of one model has been solved, its results are used to adjust or expand the data for the others. In support of this activity, several systems provide features to name different models and to switch between them by name, so that the variables of one are held fixed while optimization is performed over the variables of the other.

* This article was written while the author was a visiting member of
technical staff in the Bell Laboratories division of Lucent Technologies,
Murray Hill, NJ.*

- [1]
- R. FOURER, Modeling Languages versus Matrix Generators for Linear
Programming.
*ACM Transactions on Mathematical Software***9**(1983) 143-183. - [2]
- G. MITRA, B. KRISTJANSSON, C. LUCAS and S. MOODY, Sets and
Indices in Linear Programming Modelling and their Integration with
Relational Data Models.
*Computational Optimization and Applications***4**(1995) 263-292.

LAST MODIFIED 14 OCTOBER 1996 BY 4er.