Software Survey: Linear Programming
Eleventh in a series of LP surveys spotlights recent developments and trends.
By Robert Fourer
This is the eleventh 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 software vendors by OR/MS Today. Results are summarized by product in the tables following this article. Further information is available directly from the vendors, for whom contact information is provided at the end.
Products listed in this survey are concerned, at the least, with minimizing or maximizing linear constraints subject to linear equalities and inequalities in numerical decision variables. All products provide for continuous variables that may take any values between their bounds, and many also accommodate integer variables that are limited to whole-number values in some way. The respectively continuous and discrete problems that use these variables are commonly distinguished as linear programs (LPs) and integer or mixed-integer linear programs (IPs/ILPs or MIPs/MILPs), but for convenience “LP software” is used herein as a general term for the packages covered, and “LP” refers to linear problems that may or may not have some integer variables.
Some of the listed products handle other kinds of discrete variables and constraints, as well as varied nonlinearities and even problems outside of optimization. This survey focuses on developments and trends in the linear programming and related integer programming aspects of the software, however. Also, the listing excludes products that address only certain applications or formulations of LP, or that are not targeted to large LP instances, as these products are more properly evaluated in the context of other broad categories of optimization software. The ordering of topics that follow is roughly parallel to the organization of the tables, and terms in bold correspond to table headings.
The printed table is limited to responses available by press time, but additional responses are welcome and will be added to the Web version of the survey. To learn more, write to Online Projects Manager Patton McGinley, firstname.lastname@example.org, or go directly to the survey at www.lionhrtpub.com/ancill/lpsurvey2011.shtml.
Types of Packages
Although the products surveyed have a common purpose and share many aspects of design, they are best understood as incorporating two complementary but fundamentally different types of software. Solver software takes an instance of an LP model as input, applies one or more solution methods and returns the results. Modeling software mediates between human modelers and solvers, providing general and intuitive ways to express symbolic models, and offering features for importing data, generating problem instances, invoking solvers, analyzing results, scripting extended algorithmic schemes and interfacing to broader applications. Products of this kind are typically built around a computer modeling language either designed specifically for describing optimization models or adapted from the features of an already popular programming or scripting language.
Numerous solver and modeling products have been developed as independent applications. Thus, solvers typically support links to many modeling systems, and modeling systems offer links to many solvers. In some cases the two may be acquired as separate products and linked by the purchaser, but more commonly they are bought in bundles of various kinds. Several developers of general-purpose modeling systems arrange to offer a variety of bundled solvers, providing modelers with an easy way to benchmark competing solvers before committing to purchase one. Some solver developers also offer bundles with modeling systems. A number of the latter developers also offer integrated systems that provide a modeling environment specifically for their own solvers. Many variations on these arrangements are possible, so prospective purchasers are advised to confirm the details carefully.
Interfaces to Other Software
Since optimization models are usually developed in the context of some larger algorithmic scheme or application (or both), the ability of LP software to be embedded is often a key consideration. Thus, although virtually any of the listed products can be run as an independent application in some kind of stand-alone mode, many are available in callable library form, generally as class libraries in an object-oriented framework. A variety of programming languages are supported for this purpose, with Python showing a notable increase in popularity in the current survey.
Solver systems have long been available as callable libraries, allowing them to be embedded within an application-specific calling program as an alternative to the use of general-purpose modeling environments. Modeling systems have increasingly also become available for embedding, however, so that the considerable advantages of developing and maintaining a modeling language formulation can be carried over into application software that solves instances of a model. It is possible to embed an entire modeling system, or a particular model or an instance of a model; not all systems provide all possibilities, so some study is necessary to determine which products are right for a given project in this respect.
Most commercial LP software libraries are distributed as binaries for linking into the user’s applications. In addition, our table includes several non-commercial solvers that make their source code available, often under one of the standard open source licenses; the largest number of these are available through the COIN-OR repository (www.coin-or.org). Source code is ideal in situations where the greatest degree of flexibility is required, such as in creating new algorithms and algorithmic schemes, or in putting together specialized application packages that require optimization problems to be solved internally at numerous points. But where the emphasis is on building models, solving instances and analyzing results, it makes more sense to use software that someone else has gone to the trouble of compiling. Thus many of the open-source solvers also offer binaries for the more popular platforms.
The application development environments provided by spreadsheet and database programs have proved to be particularly useful tools for embedding LP software. At the least, most LP modeling environments can read and write common spreadsheet and database file formats. Spreadsheet packages can also accept solver add-ins whose appeal to users and convenience for development are widely appreciated. The solver add-in that comes packaged with Excel is effective for relatively small and easy problems; independent developers offer much more powerful spreadsheet options. Some can work with a variety of spreadsheet functions that go beyond the smooth arithmetic functions assumed by classical optimization software. Several scientific and statistical packages also offer LP software add-ins specifically for their products; MATLAB appears to be the most popular in this respect.
Virtually all LP modeling systems and solvers can also handle model instances expressed in simple text formats, especially the “MPS” format dating back many decades and various “LP” formats that resemble textbook examples complete with + and = signs. These formats mainly serve for submitting bug reports and for communicating benchmark problems. Modeling systems use much more general and efficient formats for communicating problem instances to solvers and for retrieving results. Each has adopted its own format, unfortunately, so that every modeler-solver link requires a different translation. There is continuing interest in a superior standard form that could express problem instances of diverse kinds, in ways that would help to integrate LP software with Web service standards like XML. Progress has been gradual, however, and no definitive standard form has been adopted as yet.
Among supported platforms, Windows remains universal. Numerous products support a variety of Unix derivatives; Linux and MacOS are most often seen, and Solaris, HP-UX and AIX are still quite common. It should be noted that MacOS support is primarily through the Unix shell underlying System X rather than through the creation of new versions that conform to a more standard Macintosh look and feel.
Solvers offering multiprocessor versions for shared memory have become widely available, as processors have evolved to multicore architectures and the number of cores available on reasonably priced high-end PCs continues to increase. Support for distributed memory remains relatively rare, as the tradeoff between cost and performance has been, up to now, less favorable, whether for standard networks of off-the-shelf workstations or highly specialized supercomputers. Distributed memory implementations may yet be encouraged, however, by the increasingly reasonable costs for racks of multicore units, which offer an attractive hybrid design.
Most LP software takes advantage of all available memory, and so most packages have been ported to the 64-bit processors that are necessary for effective support of multiple gigabytes of physical RAM. In the case of MIP solvers, the ability to take advantage of available disk space to store part of the search tree is also valuable.
For commercial packages, size-limited demo versions (often also called student versions) permit experimentation with small problem instances. They are typically full-featured versions of the software, limited only by being restricted to problem instances of up to a few hundred variables and constraints. Several modeling systems offer conveniently packaged demo versions with one or more solvers.
Most modeling language and solver developers will arrange to provide full versions of their software for testing for a limited time. Moreover for teaching and academic research a number of commercial systems are available free under reasonable conditions. Of course, open-source packages are free for any use.
A number of modeling systems and solvers are also available free for testing by submission through the Internet to the NEOS Server (www.neos-server.org). NEOS imposes no problem-size restrictions and is free of charge; it does not guarantee confidentiality or availability of service, but those may not be the key issues in initial stages of testing. Originating in the mid-1990s, NEOS was a pioneer of what would today be considered a software-as-a-service or cloud-computing platform. Two products in this year’s listing cite commercial availability of versions in the cloud, and it would not be surprising to see “cloud availability” become a regular category in future surveys.
The table shows single commercial licenses running from hundreds to thousands of dollars, but many vendors quote prices only on request. The most popular mixed-integer solvers are at the high end. Special terms are often available for multiple purchases and for site licenses or floating licenses (which permit a certain number of copies to be used anywhere in a user’s network). Since solver performance varies considerably from problem to problem and from product to product, buyers are well advised to benchmark problems of interest before deciding which products are likely to offer the best value.
Solution methods have continued to be refined for speed and reliability. For linear programs a choice between primal simplex, dual simplex and interior-point methods is standard. The bag of tricks that make up the typical MIP branch-and-bound solver continues to grow even after decades of attention, with techniques of problem reduction, cut generation and heuristic rounding being continually improved. These refinements make more integer programs tractable but also place more responsibility on the user to study and select wisely among available options. Although MIP solvers attempt to choose the best options according to characteristics of the problem at hand, these default choices cannot be relied upon to work well for all hard MIPs. Users may find it necessary to “tune” algorithmic options through experimentation; some solvers provide suggestions for making good choices, but explicitly automated tuning is still at an early stage.
Many packages seek to address their users’ needs by supporting varied specializations and generalizations of LPs and MIPs.
In the area of discrete optimization, the ideas underlying branch-and-bound search for integer programming are sufficiently powerful to handle broader classes of constraint types. Indeed, MIP solvers have long accommodated variables that take values from an arbitrary list (via special ordered sets of type 1 or SOS1 search rules) and objectives or constraints that incorporate non-convex piecewise-linear terms (via SOS2 rules). Many solvers also have special search rules to help with semi-continuous or semi-integer variables, which must lie either at zero or in a designated positive range. Additional kinds of logical constraints, such as if-then and all-different, are becoming more common as specialized search techniques are adapted from related developments in so-called constraint programming software. The distinction between integer and constraint programming is thus slowly fading, though it will not likely disappear anytime soon.
Convex quadratic objectives and constraints, in continuous or integer variables, are another popular extension as seen in the table. These include the classic positive semidefinite quadratic formulations that describe elliptical regions, as well as newer 2nd-order cone formulations that specify regions that have a conic shape. The latter are particularly versatile because a variety of non-quadratic convex function classes can be reduced to them, extending the range of applications that can be addressed. They can be solved by extensions to LP interior-point and branch-and-bound methods, though not always as easily.
The comment fields of the table describe a variety of extensions that fall under the general heading of stochastic optimization. These include classic recourse problems given distributions or scenario trees for the data, explicit chance constraints, and other formulations that seek a solution that is robust in the face of uncertainty. Implementations vary considerably due to the great variety of problem types.
Finally, a number of products listed in the table can handle some more general nonlinear problems as well. There are quite a few good solvers intended exclusively for nonlinear optimization that do not appear but that can be found in other listings and surveys.
Robert Fourer (www.iems.northwestern.edu/~4er/), professor of industrial engineering and management sciences at Northwestern University, is one of the designers of the AMPL modeling language for mathematical programming and the NEOS Server facility for optimization over the Internet. His recent interests include detection and transformation algorithms for making optimization problems amenable to a greater range of solvers and modeling language support for nontraditional optimization.