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 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 below 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, patton@lionhrtpub.com, or go directly to the survey at www.lionhrtpub.com/ancill/lpsurvey2009.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 does not incorporate solution methods; it is typically designed around a computer modeling language for expressing LP models, and offers features for reporting, model management and application development, in addition to a translator for the 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. Most modeling system developers 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 well 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, often accessible as class libraries in an object-oriented framework. Solver systems have long been available in these ways, with an application-specific calling program taking the place of a general-purpose modeling environment. Modeling systems have increasingly also become available for embedding 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 through one of the standard open source licenses (www.opensource.org). Open source 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. Even some of the open-source solvers offer binaries for the more popular platforms.

The application development environments provided by spreadsheet and database programs have proved to be particularly attractive for embedding of 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 only for 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 uses 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 more kinds, in ways that would help to integrate LP software with Web communication standards like XML. Progress has been gradual, however, and no definitive standard form can be said to be adopted as yet.

Platforms


The range of supported platforms continues to be stable. Windows remains universal, and Linux has become nearly so for products other than spreadsheet add-ins. Among other Unix variants, Solaris, HP-UX and AIX are still quite common. Support for Apple computers has increased substantially, though primarily through ports to the Unix shell of MacOS System X, rather than through the creation of new versions that conform to a more standard Macintosh look and feel.

Multiprocessor versions for shared memory have become widely available, as multicore processor architectures have become the standard and two quad-core processors have become a readily obtained configuration on high-end PCs. Support for distributed memory remains relatively rare, despite continued general interest in "grid computing" and networks of workstations. Distributed processing seems a natural fit for integer programming branch-and-bound methods, which solve independent subproblems at nodes of a huge search tree, but promising experiments with this approach do not seem to have led yet to much commercial support.

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.

Trials


Size-limited demo versions (also often 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. A number of developers also make their products conveniently available for testing and comparison over the Internet, via the NEOS Server (neos.mcs.anl.gov). 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.

Prices


The table shows individual commercial licenses running from under $500 to as much as $5,000, but many vendors quote prices only on request. 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 large 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.

Algorithms


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 increasingly sophisticated features such as branch-and-cut, branch-and-price and feasibility-seeking heuristics becoming available to a broader range of users. 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 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.

Problem Types


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 take a pre-specified value (usually zero) or lie 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 continuing to fade, though it will not likely disappear for some time yet.

Convex quadratic objectives and constraints, in continuous or integer variables, are another popular extension as seen in the table. Linear programming further extends to cone programming and to semidefinite programming, in which non-negativity of individual variables is generalized to membership in a specified pointed cone. Problems of these types find varied applications in engineering and design, and provide strong approximations to some hard combinatorial problems; a search of the Web readily yields several collections of test problems. Interior-point methods extend to solve these problems, though not so easily as in the case of LPs. Problems of these kinds are becoming more familiar as modeling languages and problem formats catch up with them.

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.

Trends


A scan of the new features doesn't reveal much of a pattern this time around. The next big advance in LP solving or modeling might be out there, but if so it hasn't made quite enough of an impact yet to be clearly identifiable as the next big thing.

Note: The information included in this survey was provided by vendors and not independently verified. Due to space limitations, not all of the vendors who responded appear in the survey. In other instances, answers to some questions were edited to fit. For a more complete survey, including vendors who responded after the deadline, go to: http://www.lionhrtpub.com/orms/surveys/LP/LP-survey.html.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2009 by the Institute for Operations Research and the Management Sciences. All rights reserved.


Lionheart Publishing, Inc.
506 Roswell Rd., 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 2009 by Lionheart Publishing, Inc. All rights reserved.