OR/MS Today - August 2001 Linear Programming Software Survey Linear Programming Solver or Modeling: Popular OR tool can take different approaches to reach common goal By Robert Fourer This is the sixth in a series of surveys of software for linear programming, dating back to 1990. As in the case of earlier surveys, information has been gathered by means of a questionnaire sent to LP software vendors by the editors of OR/MS Today. Results are summarized by product in the table following this article, after which contact details for further information are listed by vendor. Scope of the Survey The products listed in this survey are concerned with minimizing or maximizing linear constraints, subject to linear equalities and inequalities in continuous decision variables. Many of these products also deal with integer-valued variables and related kinds of variables and constraints — as indicated under the Variable Types heading — by means of a branch-and-bound approach that involves solving a series of linear programming problems. Some of the listed products also handle nonlinear programs, other kinds of combinatorial optimization problems, and problems outside of optimization. The tabulated information pertains only to the linear programming and related integer programming aspects, however. For convenience, "LP software" is used herein as a general term for the packages covered, and "LP" refers also to related problems that have some integer variables. The products surveyed thus have a common purpose, and share many aspects of design. Nevertheless, they are best understood as incorporating two complementary but fundamentally different types of software, as indicated under the Software Description/Type heading of the table. The first type is solver software, which takes an instance of an LP as input, applies one or more solution methods, and returns the results. A solver may be as simple as a single algorithm, but most offer a package of optimization methods, as well as algorithms for simplification and analysis of LPs. Some solvers are designed to be used as stand-alone programs that read files you have created, or as procedure libraries that are called from programs you have written. These tend to be marketed on the basis of the speed and reliability of their algorithms. Other solvers are intended for use within the environments of more general application packages, especially spreadsheets and mathematical software systems, and their marketing tends to stress convenience and compatibility. The distinction between solvers of these two kinds is indicated under Software Description/Form in the table. Some developers have produced solver products of both kinds using the same core algorithm implementations. The second type covered by the survey is modeling software, which provides a convenient environment for formulating, solving and analyzing LPs. These systems are typically designed around a computer modeling language for expressing LP models, and offer features for reporting, model management or application development, in addition to a translator for the language. They are marketed on the power and convenience of their languages for describing diverse real problems, and on their versatility in prototyping new models and developing associated applications. A modeling software product requires at least one solver, and many offer a choice of solvers. Some solver and modeling packages can be obtained separately and linked by the purchaser, but more commonly they are bought in bundles of various kinds. Indeed, a number of products consist of "integrated" solver and modeling components that are designed only for use together. The Solvers or modeling environments that link to this product table column indicates the modeling systems that can work with each solver and the solvers that can be used by each modeling system; vendors should be contacted for details of available bundles. General Observations As in the past, most of the packages listed in this year's survey were in existence at the time of the preceding one. The columns headed New Features, Other Techniques and Comments/Description suggest that change continues to be mainly evolutionary, though with perhaps a few significant new developments. The mix of algorithms used by software for continuous linear programming has settled down, with much the same combination of simplex and interior methods implemented in many packages. Related methods for reducing problem size and bounds (presolving) and for diagnosing the causes of infeasibility have also become standard. As more powerful computers have encouraged users to solve harder problems, however, developers have found it worthwhile to consider (or reconsider) ideas for improving specific algorithmic steps, often with substantial improvements in efficiency. The situation for algorithms that can handle any subset of integer variables — so-called mixed-integer programming or MIP algorithms — has been similar. But as MIP problems are much harder than continuous LPs of comparable size, no one combination of branch-and-bound options can give universally superior results. Thus, all of the major MIP solver developers report dramatic successes, on certain problems, with a variety of recently added techniques. These include established branch-and-bound strategies such as cutting planes, heuristic preprocessing and probing, as well as ideas from the related field of constraint programming for handling "all different" and other special constraint structures. (The boundary between integer and constraint programming is gradually softening but remains well defined for now.) Most of the products that run under the UNIX operating system on workstations also now run under Linux on PCs. At the same time, a substantial number of optimization packages are tailored to the Microsoft Windows interface and are not available on any other platforms. A variety of parallel-processing versions of solvers continue to be available, some for multiprocessor shared-memory computers and some for distributed processing on networks of workstations or PCs, but with no obvious pattern or trend. Outlook: Integration Strategies One big issue in the early days of linear programming [1, p. 15] was whether a mathematical programming system should take over the computer, or whether it should run under an operating system. Today, we take it for granted that no computer runs any user software until the operating system has been booted. An analogous change of view has been occurring in the relationship of LP packages to applications software. At one time most LP systems were conceived mainly as stand-alone products, encompassing a solver along with whatever problem-input and result-output facilities the solver might need. Today, integration with standard spreadsheet and database software is taken for granted, while the more pressing issue is how LP systems should be designed to permit the integration of optimization models into specialized application programs. Current modeling systems take a diversity of approaches to integration. One strategy extends a modeling system into a full-fledged application development environment, with facilities for creating layouts, charts, buttons and all the behavior that one expects to find in a sophisticated graphical user interface. This kind of system offers convenient application development with a minimum of programming, but does require the adoption a new development environment specifically for optimization-related problems. At the other end of the spectrum, by being implemented as an add-in, a modeling system can adopt the features of an existing development environment. Spreadsheet add-ins are well established and continue to dominate this category, but there is increasing interest in add-ins to other development tools such as databases and more general mathematical modeling environments. Perhaps the most widely investigated possibility is to apply the idea of a callable library (or in more modern terms, an application programming interface, or API). Most solvers are now available in this form, which permits their features to be accessed through function calls from any application program written in a common language such as Visual Basic or C++. Typically the application program offers a graphical interface tailored to the intended users, who may not even be aware that certain features involve calls to a solver. While the final result may have an attractive interface, however, the job of defining an optimization model through calls to a solver is anything but attractive. Initial model development tends to be slow and error-prone, while maintenance is difficult and costly. These are exactly the drawbacks for which modeling languages and systems were designed, however, and so the obvious extension is to provide a modeling system with a callable library. Under such an arrangement, the model developer (or maintainer) works directly with the modeling system in the usual way, taking advantage of the system's convenient features for manipulating formulations, algorithms and results. The finished model is then embedded in the application program through function calls to the library version of the modeling system. There are numerous variants to this approach. The application's connection to the modeling system can be relatively loose, with the application passing along model files and commands in much the same way that a model developer would, except via function calls. In a relatively tight connection, on the other hand, individual steps that a human modeler would take in using the modeling system are provided through a series of detailed function calls for setting options, acquiring data, executing a solver, extracting results and so forth. An object-oriented approach works well here, with the objects corresponding to models and their parts. Whatever the design, however, the key feature here is that the library function calls refer to the optimization problem using terms from the system's modeling language rather that through low-level concepts — like matrix row-number — that are more appropriate for use by algorithms. A final key distinction has to do with the degree to which a model and data are processed before being embedded in an application. One flexible arrangement is to pass an entire model, in the form specified by some modeling language, to the modeling system by use of the callable library. Alternatively, the application developer may be able to use the modeling system to do some amount of model translation in advance, after which only a "compiled" version is embedded within the application. This alternative can greatly reduce the amount of modeling system code that has to be included in the application. It also prevents users of the application from seeing the original model, an important concern for security-conscious developers. Certain data values may be compiled with the model, but in general an application depends on being able to optimize with different data values every time. Outlook: Service Providers Experimental "servers" for various kinds of optimization software have continued to proliferate. Many are described in a recent survey of "Optimization as an Internet Resource" in a special issue of Interfaces devoted to ORMS and E-Business [2]. Model builders are gradually becoming aware that solvers can be tested and compared over the Internet, saving the considerable trouble of downloading and installing test versions. For example number of solvers available through the NEOS Server [3] has grown to more than 40, of which a majority were added in the past two years, and the number of optimization submissions has grown to more than 2,000 per week. The idea of a callable library extends to optimization servers as well as modeling systems. In fact, the ability to call a remote optimization server is particularly appealing within a locally installed modeling system. Under such an arrangement, model developers continue to build models and analyze results as before, while their requests to "solve" are automatically handled remotely at the server. Thus up-to-date versions of many solvers are made available without any of the difficulties of installation. Some of the NEOS solvers have recently been made accessible in this way [4]. It remains to be seen how the use of optimization servers will develop. Widespread adoption will require better large-scale strategies for scheduling requests and better interfaces for helping people to choose from the many solvers available. Regular commercial service, in the form of so-called application service providers (or ASPs) for optimization, will necessitate new economic models and highly reliable server architectures. All of these needs remain subjects of research at present. Although public optimization servers have received most of the attention, the same idea might be useful within large companies and other organizations. The callability of optimization modeling systems and servers might be put to work together, moreover, to produce specialized application packages that run locally, but that optimize remotely to take advantage of the most attractive linear or integer programming resources, wherever they might happen to be. References William Orchard-Hays, "History of Mathematical Programming Systems," in Design and Implementation of Optimization Software, H.J. Greenberg, ed., Sijthoff & Noordhoff, Alphen aan den Rijn, The Netherlands (1978), 1-26. Robert Fourer and Jean-Pierre Goux, "Optimization as an Internet Resource," Interfaces, Vol. 31, No. 2 (March-April 2001), 130-150. See www-neos.mcs.anl.gov/neos/server-solvers.html. See www-neos.mcs.anl.gov/neos/kestrel.html. Be sure to read the survey online. Robert Fourer (http://www.iems.nwu.edu/~4er/), a professor in the Industrial Engineering and Management Sciences Department at Northwestern University, is one of the designers of the AMPL modeling language for mathematical programming. He maintains the Linear Programming and Nonlinear Programming Frequently Asked Questions list at www.mcs.anl.gov/home/otc/Guide/faq/ Table of Contents OR/MS Today Home Page OR/MS Today copyright © 2001 by the Institute for Operations Research and the Management Sciences. All rights reserved. Lionheart Publishing, Inc. 506 Roswell Street, Suite 220, Marietta, GA 30060, USA Phone: 770-431-0867 | Fax: 770-432-6969 E-mail: lpi@lionhrtpub.com URL: http://www.lionhrtpub.com Web Site © Copyright 2001 by Lionheart Publishing, Inc. All rights reserved.