August 1999
Linear Programming
1999 OR/MS Today survey reveals evolutionary changes to popular software, coupled with a few significant developments
By Robert Fourer
This is the fifth 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. A few developers have produced solver products of both kinds using the same core algorithm implementations, but in general the distinction between them has remained strong.
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 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 converting them to 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.
Trends and new developments
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 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. The result has been a surprising number of developers reporting substantially increased efficiency in new implementations of well-known algorithms, especially on very large LPs.
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, the improvements have been even greater. Virtually all the major MIP solver developers report improved performance in their implementations of established branch-and-bound strategies. Specifics such as "cutting planes" and "preprocessing and probing" under New Features are also well established in the technical literature, but their use in commercial software has become more extensive in recent years.
A related development is indicated by more references to "constraint programming" in the survey. Constraint programming incorporates tree-search algorithms like branch-and-bound, but uses different strategies that can be more effective for highly combinatorial problems such as scheduling, assignment and configuration. Established methods of constraint programming, which arose out of the study of logic programming in artificial intelligence, do not involve solving any linear programs. They overlap with branch-and-bound in a number of respects, however, and the boundary between the two is likely to become less well-defined in the future. Other trends identified in the previous survey that have persisted and perhaps intensified somewhat include:
- Availability of parallel-processing versions of solvers, some for multiprocessor shared-memory computers and some for distributed processing on networks of workstations or PCs.
- Integration with databases, spreadsheets and mathematical software packages.
- Extension of application-development features such as shared libraries (especially Windows DLLs), code generators and graphical interface development tools.
Also, on PCs the growing popularity of the Linux operating system has led to a much broader base of support. At the same time, a substantial number of optimization packages are tailored to the Microsoft Windows graphical interface and are not available on any other platforms.
Longer-term outlook
It is enlightening to compare this year's survey with the first one in 1990, and to extrapolate some of the changes over the next 10 years.
Limits on numbers of variables, constraints and nonzero coefficients were a significant factor in 1990's table. Today, virtually all products have no practical limit other than what is imposed by the amount of memory available, even though this amount has increased for typical computers by orders of magnitude. Problem size has never been the major limitation in the success of LP applications, however, and this is unlikely to change, despite further incredible advances in memory chips that will no doubt occur in the next decade.
The article accompanying the 1990 survey devoted most of its attention to solver software issues, such as solution speeds and problem sizes. Since then, competition in modeling software has intensified greatly, to the point that over half the entries in this year's table are characterized as modeling environments or integrated solving and modeling environments. Current modeling software is a mixture of "closed" systems in which the modeling features are designed for and integrated with particular solvers, and "open" systems encompassing solvers that can run under a variety of modeling systems and modeling systems that are designed to support a range of solvers. The trend in this respect is hard to spot at present and is even less clear for the future. Many of the products in 1990's table are to be found in this year's as well. Most of the low-cost, limited-feature solvers that proliferated in the early days of PCs have disappeared, however. Size-limited versions of full-featured products have taken over much of this part of the market. As a result, linear and integer programming are now much more likely to be taught with the same software that is used in practice. This trend is likely to continue, particularly as textbooks catch up with the complexity of examples that student software can now handle.
Finally, perhaps the most striking change over the past decade can be seen in the contact information. The only way to get in touch with any of the software vendors via their listings in the 1990 table was by writing a letter or picking up the telephone. There were no fax numbers, let alone E-mail or Web addresses. Today virtually every vendor has a Web site, so that a reader of this survey can much more easily follow up on products of interest. Free demo versions of modeling systems and associated solvers are increasingly available for downloading and evaluation. The overall level of knowledge of optimization software among potential users is thus arguably much higher, and the number of active applications shows signs of having increased as a result.
The distribution of demo software for optimization is still mainly by downloading to individual computers, however. Thus the impact of demos is constrained by the reluctance of busy modelers and cautious employers to install new software, even temporarily. Despite the many competing packages available for LP, informal evidence suggests that the average user never tries out more than a small number of them. Advances in network speeds, Web interfaces and Internet commerce over the next decade promise to help relieve this problem, by allowing solvers to be tried out effectively over the network. In fact, a variety of prototypes along this line have become available in the past few years, so that a trend may be said to be already in progress. Current Internet "optimization servers" are still limited in features, however (much as many LP solvers were limited 10 years ago). Their popularity and sophistication will tend to grow, but increasing use is likely to raise new issues of resource allocation and reliability that will need to be resolved before the Web's full potential in linear programming will be realized.
Be sure to visit the 1999 Linear Programming Survey web pages.
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/
OR/MS Today copyright 1999 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: www.lionhrtpub.com
Web Site Copyright 1999 by Lionheart Publishing, Inc. All rights reserved.