Department of Industrial Engineering and Management Sciences
Northwestern University, Evanston, IL 60208-3119
4er@iems.nwu.edu - 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:
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.
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.
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.
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
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:
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.
Return to the AMPL home page.