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:
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:
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.