Reprinted from the
INFORMS Computer Science Technical Section Newsletter, Volume 17, Number 1, Spring 1996

Software for Optimization: A Buyer's Guide
Part 1

Robert Fourer

Department of Industrial Engineering and Management Sciences
Northwestern University, Evanston, IL 60208-3119

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


The category of "optimization software" is neither small nor simple. In its survey of "Linear Programming Solver Software for Personal Computers" [6], OR/MS Today lists over three dozen features for each of 30 packages. The same issue's "OR/MS Resource Directory" [5] includes optimization software providers under several headings, including Linear/Integer Programming and Non-Linear Programming; Production Planning, Scheduling, and Transportation/Routing/Logistics; and Modeling Languages. The 151 entries under these headings represent only 87 different companies, further suggesting the difficulty of characterizing software in this area. John Gregory's lists of Frequently Asked Questions for linear and nonlinear programming [3,4] confirm that there is plenty of uncertainty (if not outright confusion) on the part of potential buyers and users of this software.

In this article, I offer 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, presented below, is directed toward relatively general market concerns:

Part 2 is focused on more specific technical matters:

My answers are somewhat biased toward products that emphasize decision-variable formulations, optimal algorithms, and other features that have become well established in the optimization software market. Nevertheless, most of the discussion is applicable to all kinds of computer systems that support optimization modeling.

One distinction that I do not make is between commercial systems that are licensed and supported for a fee, and noncommercial systems that can be freely downloaded over the Internet and have no guaranteed support. If your application demands fast and reliable execution, quick bug fixes, clear documentation, and sophisticated graphical interfaces, then you are likely to be considering rather expensive packages licensed by profit-seeking companies. On the other hand, you should not expect to find much "public domain" optimization software at any level of quality; a developer who has devoted the time necessary to create a worthwhile optimization package and to support its users is likely to have at least retained the rights to it. Between these extremes, the correlation between quality and cost is by no means exact. In particular, a number of well-known and highly reputed packages are "semi-commercial" in some sense: sold at a low price, or distributed free for academic research, or supported voluntarily by their developers as time permits.

My analysis also makes no special distinction for "educational" software. Back when computer time was scarce and interfaces were primitive, college courses came to rely on the simplistic interfaces and slow, unreliable algorithms of "student" optimization packages whose performance was adequate for small illustrations and exercises. Today's more fortunate students can be taught with the same packages that practitioners use for applications of realistic size and complexity. Many such packages are available at low academic prices, with the least expensive versions being limited to some reasonably sufficient number of variables and constraints.

One final caution: my answers unavoidably make the implicit assumption that you have some kind of problem that an optimization model can help with. Before beginning to evaluate optimization software, there are broader questions that you presumably have asked: What is the problem you face? What are you trying to accomplish in addressing that problem? What approaches have a chance of succeeding? How large an investment in these approaches can be justified? Though beyond the scope of this article, these are questions that ought to be familiar to anyone who is attempting to apply mathematical modeling techniques.



Part 1. Market Considerations


What optimization problems does the product address?

There is no Universal Optimizer that is well suited to any kind of optimization problem whatsoever. Both the interface demands of users and the mathematical properties of algorithms tend to enforce a degree of specialization upon optimization systems. Nevertheless, successful systems differ considerably in the degree of specialization that they adopt.

At one extreme are systems designed to address a particular optimization problem at a unique company or facility. Often, the only way to acquire such a system is to build it yourself (or to hire your own consultant to build it); after all, if it were used anywhere previously then it would be specialized to someone else's operation, not yours. Sometimes a specialized system for a similar operation can be rebuilt, however, to cater to your needs as well.

After a specialized optimization system has been rebuilt a few times for different users, it may evolve into a package that can meet the needs of an industry rather than only a particular enterprise. Packages of this sort can be designed from scratch as well, but they are usually most successful when their design has been refined by a few particular customers. There are packages specially designed for scheduling assembly lines, for example, and for scheduling airline crews, and even for scheduling school buses.

A further level of generalization is accomplished by systems that address a particular area of optimization needs, by focusing on problem characteristics that transcend individual application areas. Thus there are systems designed to help you deal with problems characteristic of scheduling, no matter what your industry or organization of origin. These systems motivated the above-cited Scheduling category in the OR/MS Resource Directory [5]; the Production Planning category is another example. The Transportation/Routing/Logistics category collects software from three more areas, which are closely enough related so as to be combined in some packages. To these we could add the Networks category, which reflects software specialized to the area of network design, but encompassing the networks that arise in many different applications.

One final degree of generalization produces packages devoted to a particular mathematical class of optimization problems, independent of the area of origin. The one spectacular success in this respect has been linear programming software, which has evolved to be fast and reliable for a wide variety of problems that have little in common except the mathematical form of their objectives and constraints. The success of general LP software has been so great, in fact, as to encourage over-confidence in software for other, harder mathematical problem classes. Nevertheless, recent years have seen increasing success in general-purpose software for certain classes of nonlinear and discrete optimization problems.

When it comes to the generality of the problems addressed, the purchaser of optimization software evidently has plenty of choice. Different levels of specialization offer different combinations of strengths and weaknesses, whose tradeoffs can vary greatly from one project to the next. Typically, greater specialization permits systems that demand less mathematical expertise of the user, while incorporating more knowledge that is specific to an application; specialized scheduling software, for example, can display its results in whatever variety of tables and graphs are most appropriate and familiar to experts in the application at hand. In contrast, greater generality permits systems to address a more varied range of problems, including those for which no one has yet thought to design any specialized optimization software.

You might reasonably expect that, at this late date, specialized systems would be available for almost any optimization problem that naturally arises in commerce and industry. But in fact, it is only too easy to identify a new problem just different enough that its solution can only be regarded as unstudied, or at least unimplemented. General-purpose optimization software is thus by no means obsolete. In one familiar scenario, a new problem is explored first by experts in optimization, through a series of prototypes built with general-purpose software. Subsequently, once its formulation and solution as an optimization problem are better understood, the problem is incorporated into specialized software that can be disseminated to a broader audience of experts in the application area.


What aspects of optimization modeling does the product address?

Putting aside temporarily the differences between applications, it is possible to identify certain common aspects of optimization modeling projects. Most attempts to apply optimization involve, for example,

A more detailed discussion of these steps in the "modeling life-cycle" can be found in Geoffrion's introduction to Structured Modeling [2]. A prospective user should be aware that most optimization software packages support only some of these steps, or support some much more extensively than others. Of the many possible combinations, a few are worth special mention as being particularly common.

A solver is concerned primarily with solving individual mathematical programs (the third item above). Solvers are thus distinguished by the algorithms they implement, and by the mathematical categories of optimization problems for which they are able to find optimal solutions. One of the more common mistakes in optimization modeling is to assume that once you have found a solver that can handle the kind of problem you anticipate, your optimization software needs have been met. In reality this is true only if you are prepared to carry out the other aspects of your application using the limited data input and reporting facilities that the solver provides. You may be required, for example, to supply input as a list of coefficients in some fixed format, and to deal with results in the form of a table of all variables' values. This work can be managed "by hand" in the case of very small problems, but it requires additional computer software for optimization at any realistic scale.

One time-honored approach is to write all of the additional software yourself, using a general-purpose programming language such as C or C++, or a language specialized to some purpose other than optimization -- say, the language supported by a database management system (such as SQL) or a language for building graphical user interfaces (such as Visual Basic). Programs of this sort are known loosely as matrix generators because one of their jobs (at least in the case of linearly constrained optimization) is to generate the nonzero elements of the constraint matrix; but they also serve as sophisticated solver "front ends" that organize many aspects of input and reporting. To facilitate the construction of programs of this kind, many solvers can be obtained in the form of a callable library, a structured and documented collection of procedures. Some callable libraries are available in especially convenient packages, for example in the form of a dynamic link library (DLL) for Microsoft Windows.

Another popular approach is to employ a second, complementary optimization package to handle some or all aspects of modeling outside of the solver. A product that fulfills this role is often known (somewhat inaccurately) as a modeling language, because it is designed around some computer-readable representation of optimization problems. Its essential component is a translator that reads a model and data expressed in the modeling language, and builds the low-level representation (such as a list of coefficients) that a chosen solver requires. Additional components may handle analysis and display of results, exchange of data and results with other applications such as databases, and management of data scenarios. What appears to the casual observer to be a single optimization modeling system is thus often the result of two purchases, one of a solver and one of a modeling language. Both the language and the degree of integration with the solver vary greatly from one product to the next; some popular combinations are cited in Part 2 of this article.

Finally, some products do integrate more-or-less all of the solver and modeling language software into a single package. Such an arrangement insures a single source of support for the whole system, but forces (or strongly encourages) the use of a particular solver. Thus it tends to be most popular in situations where the speed and versatility of the solver are not the most important issues. This is often the case in relatively specialized systems, where the quality of the interface may be the most important aspect, and the range of problems with which the solver must deal is relatively narrow and well-defined. An integrated solver is also more likely to be found in the relatively small-scale and inexpensive systems used for demonstrations and prototypes. This category includes some of the more elementary modeling languages, as well as the optimization tools built into popular spreadsheet programs.


What aspects of optimization modeling does the vendor address?

While sizing up the available software, you should also evaluate more generally what the vendors are offering to sell, and to whom. Optimization software comes in any of several forms, addressed to any of several kinds of users; hardware and services may also be involved. Some vendors may not offer a broad enough range of products to meet your needs, while others may have a motivation to sell more than you want.

At one time, each of the major mainframe computer manufacturers encouraged sales of its hardware by developing and maintaining a mathematical programming package. As proprietary computer architectures have fallen out of favor, however, this practice has largely disappeared. The few exceptions in recent years have involved manufacturers of expensive multi-processor computers, for which specialized and machine-specific solvers may still be a worthwhile investment. Even in these cases, standardization is more common than in the past. Recent machine-specific optimization software has tended to be developed through extensions to existing, more portable codes, so as to facilitate adaptation to any new (and hopefully better) computing architectures that may appear.

The market for optimization products has thus come to be dominated by software vendors. Within this category, there remains a great deal of variation in the products being sold, reflecting an equally great variation in the people who buy them. Customers for these products can be roughly characterized as

These roles may or may not be played by distinct individuals. Vendors tend to focus on one of them, even though their products may address the needs of all three to some extent.

Another important distinction concerns the design of optimization products relative to the overall computing environment. Most common are the stand-alone modeling systems, which are intended to provide your entire interface to the formulation, solution and analysis stages of modeling. Newer designs offer diverse interactive and batch modes of operation, together with extended modeling languages that can serve as programming languages for building large-scale iterative schemes. At the same time, there are also a variety of alternatives to the stand-alone paradigm, which can be differentiated by the ways in which they interact with the overall environment to provide a framework for optimization:

The distinctions between these kinds of software are not always precise. As an example, current spreadsheets offer both optimization add-ins and application development environments.

Stand-alone systems tend to be most advantageous at the prototyping stage, where your work is focused on building an acceptable model and demonstrating sufficiently promising results to justify a larger investment. Although models employed for strategic planning [1] may remain at this stage, many reach a point at which the model has been validated and the needs of application users have become paramount; it is at this point that the other kinds of systems can become more attractive. For large and difficult applications, it can be worth the trouble to implement the model a second time, using a system more suitable to application building. As an alternative, some products have been extended so that they can function in modes other than the one they were first designed for. There are ways of building application shells around stand-alone systems, for example, while application development environments usually offer a stand-alone mode for prototyping.

Finally, a majority of companies that sell optimization software derive a substantial portion of their income from the sale of related services. At the least, they are likely to charge a fee for providing updated versions that incorporate bug fixes and new features. Many vendors offer considerably broader and more customized services, in such areas as software development, documentation, training, consulting, and maintenance. In extreme cases, the software is not intended to be installed or run by any customer, but is rather a base upon which a different specialized system is implemented and maintained for each customer by the vendor's expert staff. Other vendors prefer to eventually turn operational responsibility over to you, but require -- or at least strongly encourage -- the purchase of training and maintenance services as a package with the software. In contrast, an increasing number of optimization software products are designed to be run "out of the box" like any spreadsheet or word processing package, with the interaction between customer and vendor possibly limited to the initial sale.

As a consumer of optimization software, you should take care that all necessary services are budgeted at the outset, and that prospective vendors can provide such services. In some cases, a vendor that does not provide services itself may be able to recommend a consultant who has sufficient experience with its product to meet your needs.

Part 2, Technical Considerations, describes and contrasts the abilities of optimization systems to express, solve, analyze, debug and maintain models and data.

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.


References

[1]
J. BISSCHOP and A. MEERAUS, On the Development of a General Algebraic Modeling System in a Strategic Planning Environment. Mathematical Programming Study 20 (1982) 1-29.

[2]
A.M. GEOFFRION, An Introduction to Structured Modeling. Management Science 33 (1987) 547-588.

[3]
R. FOURER and J.W. GREGORY, Linear Programming -- Frequently Asked Questions List. Posted to sci.op-research; archived at http://www.mcs.anl.gov/home/otc/ Guide/faq/.

[4]
R. FOURER and J.W. GREGORY, Nonlinear Programming -- Frequently Asked Questions List. Posted to sci.op-research; archived at http://www.mcs.anl.gov/home/otc/ Guide/faq/.

[5]
1995 OR/MS Resource Directory. OR/MS Today 22:5 (1995) 75-96.

[6]
R. SHARDA, Linear Programming Solver Software for Personal Computers: 1995 Report. OR/MS Today 22:5 (1995) 49-57.



Proceed to Part 2.

Return to the AMPL home page.


LAST MODIFIED 14 OCTOBER 1996 BY 4er.