April 1997 • Volume 24 • Number 2
Software Survey: Linear Programming
1997 update indicates change has mainly been evolutionary, but a few significant trends emerge
By Robert Fourer
This is the fourth in a series of surveys of software for linear programming. As in the case of earlier surveys in 1990, 1992 and 1995, 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 are listed.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 as shown under the "Integer Programming" heading of the table, and related kinds of variables and constraints as indicated under "Algorithms & Features" and "Other Techniques." Some also handle nonlinear programs and other kinds of combinatorial optimization problems, as well as problems in statistics and other areas of business and scientific computing. The tabulated information, however, pertains only to the linear programming parts, and for convenience, all products are herein referred to as "LP software."
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 kinds of software.
On the one hand is solver software that takes a description of a particular 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. Solver software can be used alone, provided you are willing to develop any programs necessary for preparing input and processing results. Many solvers also have links to a variety of modeling packages that will do some of this work for you, as indicated under the "Modeling & Analysis Software" heading.
The latter packages represent modeling software that provides a convenient environment for formulating, solving and analyzing LPs. A typical modeling system is designed around a computer language for expressing LP models, and offers features for reporting, model management or application development in addition to a translator for the language. Modeling systems require a solver, and typically offer a choice of them as also indicated in the table.
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. Available configurations are suggested in the table under "Modeling & Analysis Software," with additional information under "Algorithms & Features" and "Comments," but there are too many combinations to list all possibilities; vendors should be contacted for details.
Trends and new developments
Most of the packages listed in this version of the OR/MS Today survey were in existence at the time of the preceding survey. The "New Features" and "Other Techniques" columns suggest that change has mainly been evolutionary, but do point to a few significant trends.
An increasing number of products offer interior-point methods, which have become an established complement to variants of the simplex method in solvers for linear programs in continuous variables. Each kind of method has turned out to have its advantages, and neither shows any sign of being supplanted by the other.
Parallel processing implementations continue to grow in number, motivated mainly by the savings to be achieved in parallelizing the branch-and-bound method for integer programming. This trend has two distinct parts. Implementations for shared-memory computer architectures have been spurred by fast multi-processor versions of popular Unix workstations. They address the market once dominated by proprietary mainframe and supercomputer architectures, in which large expenditures on "number-crunching" machines can be justified by the large benefits to be gained from the results. On the other hand, implementations for distributed-memory parallelization have been motivated by the availability of unused computing time on networked single-processor workstations or PCs. The idea of carrying out huge computations on networks of workstations is hardly new, but the commercial niches for this approach are still in the process of being established in the LP market.
Access to databases and support of database applications from LP software continue to grow. In the PC world, standards such as ODBC are allowing optimization packages to communicate in a uniform way with a broad variety of database software, and even database ranges in spreadsheets. Meanwhile spreadsheet-based optimizers continue to be popular.
Indeed, there is a more general trend toward LP systems that can participate in the broader process of system development, rather than standing alone as the primary systems of interest. Like several of the other trends just mentioned, this one is not new by any means, but seems to be gathering steam. Signs include the growing number of solvers available in callable library form -- especially as DLLs for Windows -- and the proliferation in LP modeling software of such features as application development environments and run-time licenses.
Finally, the growth of the Internet has helped to make optimization software more visible to potential users. In his article accompanying the 1995 survey, Ramesh Sharda observed that the summary table "includes E-mail addresses for a majority of vendors" and that "some vendors have set up home pages on the World Wide Web to stay in touch with their customers." Today almost all of the listed products provide detailed information through a Web site, while some are beginning to offer downloadable demos and remote execution of solvers over the Internet.
Comments on the table
Aside from the table columns mentioned above, most are self-explanatory. The following merit some additional comment or clarification.
Platform. The 1995 survey was titled "Linear Programming Solver Software for Personal Computers," but it is now safe to say that virtually all LP software runs on PCs, like software of any other kind. LP products do vary considerably in the degree to which they adopt the conventions of one version or another of Microsoft Windows, but this is a distinction not readily captured in a survey; the table indicates only whether a package's vendor has indicated that it is able to run under DOS, Windows 95 or Windows NT. Unix workstations as a group are the next most common platform.
Size of problem solvable. Where the "smallest version" listed in this part of the table is under 1,000 rows (constraints) and columns (variables), it is most likely the vendor's low-cost demo or "educational" version. While unsuitable for many practical applications, such a version often proves to be the most convenient source of information on the look and feel of the PC interface. At the other end of the scale, the "largest version" is commonly limited only by available system resources. Some solvers are subject to more restrictive limits, however, due to design limitations such as the use of short integers to hold row numbers. As processors have continued to get faster, disks larger and RAM cheaper, such arbitrary limits have become more significant, especially for non-integer linear programming.
Pricing. Many vendors offer a restricted version of their product for a few hundred dollars or less, to encourage its use for teaching or evaluation. Short-term demonstration copies are also often available (though not listed in the table) at no charge. Versions unrestricted as to problem size tend to be more expensive than common PC software, however, with prices in thousands of dollars per processor being average. Most vendors offer a range of prices, however, depending on the algorithms and features included, the platform and number of processors licensed, and the additional software bundled. The prices in the table should thus be considered only a rough indicator that can serve as a starting point for evaluation.
Input formats. Virtually all of the optimization products can read and write data as text files in some format. The archaic MPS input format is often supported for compatibility. Many products support text and binary formats that are more compact and flexible, however, such as the formats employed by various LP modeling packages.
Spreadsheet compatibility. Solvers included with the major spreadsheet packages have remained highly popular. As shown in the survey table, the developers of these spreadsheet optimizers offer larger and more powerful versions at extra cost, while a number of other LP products can at least read or write spreadsheet files.
Go to the online version of the 1997 Linear Programming Survey
Robert Fourer, 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 lists at www.mcs.anl.gov/home/otc/Guide/faq/ ,and can be reached via his home page at iems.nwu.edu/~4er/.
E-mail to the Editorial Department of OR/MS Today: orms@lionhrtpub.com
OR/MS Today copyright 1997, 1998 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
2555 Cumberland Parkway, Suite 299, Atlanta, GA 30339 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
Web Site Copyright 1997, 1998 by Lionheart Publishing, Inc. All rights reserved.
Web Design by Premier Web Designs, e-mail lionwebmaster@preweb.com