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 programs (IPs or MIPs), 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. Indeed a trend toward greater generality in recent years continues to be seen. This survey focuses on developments and trends in the linear programming and related integer programming aspects of the software, however. The ordering of topics below is roughly parallel to the organization of the tables, and terms in bold correspond to table headings.

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/lpsurvey2007.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 in 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, 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 through one of the standard open source licenses (www.opensource.org); a Web search will turn up several others that are under active development (but that generated no response to our survey). 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 a few of 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-ins that come packaged with spreadsheet products are effective only for small and easy problems, but 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. Linux, Solaris, HP-UX, AIX and other varieties of Unix are quite common, especially where no sophisticated graphical user interface is involved. Support for Apple MacOS continues to increase gradually. Developers who list it under Other Unix have presumably ported it to the underlying Unix shell of MacOS System X; those who list it under Other OS may or may not have created new versions that conform to a more standard Macintosh look and feel.

Multiprocessor versions for shared memory have become widely available, to support multi-processor workstations and the new "multi-core" processor designs that put two, four or more processing units on one chip. Support for distributed memory remains rare, despite increasing 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 whatever computer memory is available, and so an increasing number of packages are being ported to the 64-bit processors that are necessary for effective support of multiple gigabytes of physical memory. 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 (www-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 these are not usually the key issues in initial stages of testing.

Prices


The table shows individual commercial licenses running from under $500 to more than $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 developers choose default settings carefully, often by means of proprietary heuristics, defaults cannot be relied upon to work well for all hard MIPs; even a simple upgrade from one version of a package to the next may necessitate an adjustment to the option settings.

Problem types


Developers continue to look for ways to address their customers' needs by supporting new 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 variables, which must either take a prespecified value (usually zero) or lie in a designated continuous range. Additional kinds of logical constraints, such as if-then and all-different, are gradually becoming more common as specialized search techniques are adapted from related developments in constraint programming software. The distinction between integer programming and constraint programming is thus continuing to fade, though it will not disappear for some time yet.

Convex quadratic objectives and constraints, in continuous or integer variables, are other popular extensions 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 likely to become more familiar once modeling languages and standard 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 specifically for nonlinear optimization that do not appear, but that can be found in other listings and surveys.

What's on the horizon? Combinations of mixed-integer and nonlinear programming have been a recent focus of intensive solver development, driven by applications in such areas as engineering design, power control and financial management. Problems of this kind potentially combine all of the challenges of integer programming with all of the quite different challenges of nonlinear programming, and yet a combination of new ideas, better implementations and more powerful computers has begun to offer greater hope for getting acceptable solutions (if not solving them outright to optimality). Again, collections of test problems from various sources can be found by a quick Web search.

View the Linear Programming Software Survey




Robert Fourer (www.iems.northwestern.edu/~4er/), professor of Industrial Engineering and Management Sciences at Northwestern University and a member of the Optimization Technology Center of Northwestern and Argonne National Laboratory, is one of the designers of the AMPL modeling language for mathematical programming and the NEOS Server facility for optimization over the Internet. Recently he has been active in attempts to establish new standard forms for optimization problem instances.

Table of Contents

OR/MS Today Home Page


OR/MS Today copyright © 2007 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 2007 by Lionheart Publishing, Inc. All rights reserved.