OR/MS Today - June 2005|
Eighth in a series of LP surveys highlights recent trends in profession's most popular software.
By Robert Fourer
This is the eighth 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 the editors of OR/MS Today. Results are summarized by product in the tables following this article, after which contact details for further information are listed by vendor.
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, there has been a trend toward greater generality in recent years. This survey focuses on developments and trends in the linear programming and related integer programming aspects of the software. The ordering of topics 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, firstname.lastname@example.org, or go directly to the survey at www.lionhrtpub.com/ancill/lpsurvey2005.shtml.
Numerous solver and modeling products have been developed as independent applications. Thus, solvers typically support links to many modeling systems, and modeling systems work with 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 that prospective purchasers are well advised to confirm the details carefully.
Most commercial LP software libraries are distributed as binaries for linking into the user's applications. In addition to the few offering source code that are listed in our table, several non-commercial solvers make their code available through one of the standard open-source licenses (www.opensource.org). Currently the most prominent open-source LP codes include GLPK (www.gnu.org/software/glpk/glpk.html) and lp_solve (groups.yahoo.com/group/lp_solve/), which also have interfaces to MathProg, an open-source modeling language; and CBC/CLP, available at the COIN-OR site (www.coin-or.org) along with packages for building specialized branching schemes for solving mixed-integer programs. 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 somewhere inside. But where the emphasis is on building models, solving instances and analyzing results, it makes more sense to use commercial software that someone else has gone to the trouble of compiling and debugging. Demonstration versions of commercial codes are often available (see further below) and even for open-source projects there are often compiled binaries available for the most common 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; much more powerful LP software add-in options are available for separate purchase. Several developers of scientific and statistical packages also offer LP software add-ins specifically for their products.
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. Possibilities for a superior standard form for model instances continue to receive growing attention, particularly XML-based forms that would facilitate the integration of LP software with Web communication standards. Many interconnected issues must be addressed in devising a new standard, however, and in the case of LP there is the additional complication of wanting a standard that will extend well to other kinds of optimization models of interest.
Multiprocessor versions for shared memory have become more widely available, as multiple processors have become more of a standard for high-end workstations. Undoubtedly there will be support as well for the new "dual core" designs that put two processors 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.
A very fast dual-processor PC with multiple gigabytes of memory is thus perhaps the platform of choice for very large LPs or very hard MIPs. LP software continues to become increasingly available for the 64-bit processors that are necessary for effective support of more than 4 gigabytes of physical memory and that may offer better performance even for smaller memory amounts.
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 are conveniently packaged in 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 the key issues in initial stages of testing.
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.
Spreadsheets are also proving to have a strong influence in discreet optimization. A spreadsheet solver uses expressions in certain cells to specify objective and constraint functions, so users naturally expect to be able to employ whatever expressions the spreadsheet program makes available. Quite a few of these are logical, non-smooth or even discontinuous, however, necessitating extensions to existing optimization methods.
Convex quadratic objectives and constraints, in continuous or integer variables, are another popular extension as seen in the table. Convex quadratically constrained quadratic programming further extends to so-called second-order cone programming, and to semidefinite programming where non-negativity of individual variables is generalized to positive semidefiniteness of symmetric matrices of variables. Problems of these types find varied applications in engineering and design, and provide strong approximations to some hard combinatorial problems; some examples can be found at www.gamsworld.org/cone/conelib.htm. Interior-point methods extend to solve these problems, though not with the same ease as LP problems. Modeling languages are only beginning to catch up with these problems; they are likely to become more familiar once modeling systems more fully support 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 next? The complementary slackness conditions for optimality of linear programs can be viewed as a special case of a complementarity or equilibrium constraint. In the simplest case, such a constraint requires two inequalities to be satisfied, at least one with equality. Specialized solvers have long been available for equilibrium problems consisting entirely of such constraints. But recent work has made great progress in solvers for the more general case of mathematical programs with complementarity (or equilibrium) constraints MPCCs or MPECs for short. These problems have varied applications from economics to engineering, as can be seen in the MPEC Library collected at www.gamsworld.org/mpec/mpeclib.htm.
OR/MS Today copyright © 2005 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
Web Site © Copyright 2005 by Lionheart Publishing, Inc. All rights reserved.