Operations Research Management Science - Linear Programming Software Survey

<BODY bgcolor="#ffffff" link="cc0000" vlink="cc0000" text="#000000"> <img src="../cleardot.gif" width=1 height=1 vspace=4 border=0><br>   <table border=0 cellspacing=0 cellpadding=0 width=480><tr valign=top> <td width=10><img src="../cleardot.gif" width=1 height=1 hspace=4 border=0></td> <td width=470> <FONT face="verdana, arial, helvetica" SIZE=2><B><I><A HREF="../../ORMS.shtml" TARGET="_top">OR/MS Today</A> - December 2003</I></B></font><BR> <hr size="1"> <img src="cleardot.gif" width=1 height=1 vspace=4 border=0><br> <font face="times new roman, times"> <img src="../cleardot.gif" width=1 height=1 vspace=4 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=2><B>Software Survey</B></FONT><br> <IMG SRC="../barbluehook.gif" WIDTH="468" HEIGHT="4"><br> <img src="../cleardot.gif" width=1 height=1 vspace=8 border=0><br> <FONT SIZE="+2"><B>Linear Programming</B></FONT><BR> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> <FONT SIZE="+1"><I>Seventh in a series of LP surveys spotlights trend toward broadening scope of optimization software.</I></FONT><BR> <img src="../cleardot.gif" width=1 height=1 vspace=6 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=2><B>By Robert Fourer</B></FONT><br> <hr size="1"> <img src="../cleardot.gif" width=1 height=1 vspace=12 border=0><br>    This is the seventh in a series of surveys of <A HREF="../surveys/LP/LP-survey.html" TARGET="_top"><B>software for linear programming</B></A>, 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 <I>OR/MS Today.</I> Results are summarized by product in the tables following this article, after which contact details for further information are listed by vendor. <P>Additional responses are welcome and will be added to the Web version of the survey. To receive a questionnaire, send an e-mail message to Online Projects Manager Patton McGinley: <A HREF="mailto:patton@lionhrtpub.com">patton@lionhrtpub.com</A>. <P>This article comments on new developments and trends in LP software. The ordering of topics is roughly parallel to the organization of the tables. Terms in bold correspond to table headings.<BR> <img src="../cleardot.gif" width=1 height=1 vspace=12 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=3><B>Type of package</B></FONT><BR> <IMG SRC="../barbluehook.gif" WIDTH="468" HEIGHT="4"><br> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> 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 variables that may take any values between their bounds, and many also accommodate variables that are limited to integer values in some way. The respectively continuous and discrete problems that use these variables are commonly distinguished as linear programs (LPs) and mixed-integer programs (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. <P>Some of the listed products handle other kinds of discrete variables and constraints, as well as nonlinear programs and even problems outside of optimization. The tabulated information pertains to the linear programming and related integer programming aspects, except as indicated otherwise. The broadening scope of LP software is a continuing trend, however, to which this article will return later. <P>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. <B>Solver</B> software takes an instance of an LP model as input, applies one or more solution methods, and returns the results. <B>Modeling</B> software, typically designed around a computer modeling language for expressing LP models, offers features for reporting, model management and application development, in addition to a translator for the language. <P>Many solver and modeling products have been developed as <B>independent</B> applications. Thus, solvers typically support <B>links</B> to many modeling systems, and modeling systems work with many solvers. In some cases the two may be acquired as <B>separate</B> products and linked by the purchaser, but more commonly they are bought in <B>bundles</B> 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 <B>integrated</B> systems that provide a modeling environment specifically for their own solvers. Many variations on these arrangements are possible, so that prospective purchases are well advised to confirm the details carefully.<BR> <img src="../cleardot.gif" width=1 height=1 vspace=12 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=3><B>Interfaces to other software</B></FONT><BR> <IMG SRC="../barbluehook.gif" WIDTH="468" HEIGHT="4"><br> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> 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 <I>embedded</I> is often a key consideration. Thus, although virtually any of the listed products can be run in some kind of stand-alone mode, many are available in <B>callable library</B> form, and an increasing number can be accessed as <B>class libraries</B> in an object-oriented framework. Solver systems have long been available in this form, with the 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. <P>Most commercial LP software libraries are distributed as binaries for linking into the user's applications. In addition to the few offering <B>source code</B> that are listed in our table, several non-commercial solvers make their source available. A number of open source solvers are maintained at the COIN-OR site (<A HREF="http://www.coin-or.org" TARGET="_new">www.coin-or.org</A>), while GLPK (<A HREF="http://www.gnu.org/software/glpk/glpk.html" TARGET="_new">www.gnu.org/software/glpk/glpk.html</A>) includes C source for LP and MIP solvers and a modeling language. <P>The application development environments provided by <B>spreadsheet</B> and <B>database</B> 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 <B>add-ins</B> 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. <P>Most LP modeling systems and solvers can also handle model instances expressed in simple <B>text</B> formats, mainly 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 are receiving increasingly serious attention, however. In particular an XML-based form would facilitate the integration of LP software with Web service standards now coming into wider use.<BR> <img src="../cleardot.gif" width=1 height=1 vspace=12 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=3><B>Platforms</B></FONT><BR> <IMG SRC="../barbluehook.gif" WIDTH="468" HEIGHT="4"><br> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> The range of supported platforms has seen little change. <B>Windows</B> remains universal. <B>Linux, Solaris</B> and other varieties of Unix are quite common, especially where no sophisticated graphical user interface is involved; even some of the Apple Macintosh versions are really ports to the underlying Unix shell of <B>MacOS System X.</B> <P>The availability of multiprocessor versions has not changed much, for either shared or distributed memory. A very fast single-processor PC with multiple gigabytes of RAM still appears to be the platform of choice for very large LPs or very hard MIPs. LP software is becoming increasingly available for the 64-bit processors that are necessary for support of more than a few gigabytes.<BR> <img src="../cleardot.gif" width=1 height=1 vspace=12 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=3><B>Sizes</B></FONT><BR> <IMG SRC="../barbluehook.gif" WIDTH="468" HEIGHT="4"><br> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> Most LP software can take advantage of whatever computer <B>memory</B> is available. For MIP solvers, the ability to take advantage of available <B>disk space</B> to store part of the search tree is also important. <P>The limited demo and "student" versions of solvers are often most useful in conjunction with a modeling system. Several modeling systems conveniently offer their own demo versions packaged with one or more solvers. Less restricted versions of some products can also be tried out over the Internet by use of the NEOS Server (<A HREF="http://www-neos.mcs.anl.gov" TARGET="_new">www-neos.mcs.anl.gov</A>).<BR> <img src="../cleardot.gif" width=1 height=1 vspace=12 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=3><B>Prices</B></FONT><BR> <IMG SRC="../barbluehook.gif" WIDTH="468" HEIGHT="4"><br> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> The table shows individual commercial licenses running from $500 to $5,000 and more, but many vendors quote <B>prices</B> only on request, especially for licensing on more than a single-machine basis. 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 to price out.<BR> <img src="../cleardot.gif" width=1 height=1 vspace=12 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=3><B>Algorithms</B></FONT><BR> <IMG SRC="../barbluehook.gif" WIDTH="468" HEIGHT="4"><br> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> Solution methods have continued to be refined for speed and reliability. For linear programs a choice between <B>simplex</B> (primal or dual) and <B>interior-point</B> methods is now standard. The bag of tricks that make up the typical MIP solver has continued to grow, making more integer programs tractable but also placing more responsibility on the user to study and select wisely among available options. Although developers choose preset options carefully, often by means of proprietary heuristics, the default settings cannot be relied upon to work well for all hard MIPs; options sometimes even have to be adjusted from one version of a package to the next.<BR> <img src="../cleardot.gif" width=1 height=1 vspace=12 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=3><B>Problem types</B></FONT><BR> <IMG SRC="../barbluehook.gif" WIDTH="468" HEIGHT="4"><br> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> Developers continue to extend the scope of LP software in two complementary ways. Some products offer valuable features for specialized problem types, to make them easier to represent or to solve; prominent examples are network flow optimization and stochastic programming. Others products seek to address a broader range of problems. <P>In the area of discrete optimization, the ideas underlying branch-and-bound search for <B>integer</B> 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 <B>SOS1</B> search rules) and objectives or constraints that incorporate non-convex piecewise-linear terms (via <B>SOS2</B> rules). Many solvers also have special search rules to help with semi-continuous variables, which must either take a prespecified value 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. <P><B>Convex quadratic</B> objectives and constraints, in continuous or integer variables, are another increasingly common extension. Such objectives arise, for example, from variance terms in portfolio optimization problems; integrality can be a result of the fixed units in which securities can be purchased or investments made. Both simplex-based and interior-point methods generalize readily to the convex quadratic case. <P>Convex quadratically constrained quadratic programming further extends to so-called second-order cone programming, which in turn is a case of <B>semidefinite</B> 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. Interior-point methods extend to solve them, though not with the same ease as they solve LP problems. Modeling languages are only beginning to catch up with these problems; they are likely to become more familiar once modeling systems fully support them. <P>Interior-point methods can be motivated as solving directly the fundamental optimality conditions for various problem types. Several developers have indeed generalized this approach to arbitrary smooth nonlinearly constrained nonlinear optimization, though then only <I>local</I> optimality of the results can be guaranteed. Interior-point methods are competitive in this realm with "active set" methods that can be viewed as generalization of the simplex approach. Such generalizations are outside the scope of this survey, but their existence points out the fact that LP software cannot be considered in isolation from software for other kinds of optimization. <P>Indeed, recent interest has focused on a further generalization to <I>global</I> optimization over nonlinear objectives and constraints. Several promising implementations are based on branch-and-bound strategies typical of MIP software, and naturally these can handle nonlinear integer programs as well. One can envision the concept of an LP software survey gradually becoming obsolete, as ideas for solving a variety of harder optimization problems are consolidated. <BR> <img src="../cleardot.gif" width=1 height=1 vspace=4 border=0><br> <IMG SRC="../barbluehook.gif" WIDTH="468" HEIGHT="4"><br> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=2><I><B>Robert Fourer</B> (<A HREF="http://www.iems.northwestern.edu/~4er/" TARGET="_new">www.iems.northwestern.edu/~4er/</A>), 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. He maintains the Linear Programming and Nonlinear Programming Frequently Asked Questions lists at <A HREF="http://www.mcs.anl.gov/home/otc/Guide/faq/" TARGET="_new">www.mcs.anl.gov/home/otc/Guide/faq/</A>.</i></font><BR>  <img src="../cleardot.gif" width=1 height=1 vspace=5 border=0><br>  <img src="../barblue.gif" width=468 height=1 border=0 alt=" "><br> <img src="../cleardot.gif" width=1 height=1 vspace=8 border=0><br> <CENTER><script type="text/javascript"></script> <script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"> </script></CENTER><br> <img src="../cleardot.gif" width=1 height=1 vspace=8 border=0><br> <FONT face="verdana, arial, helvetica" SIZE=1> <LI> <A HREF="tocfr.html" Target="_top"><I>Table of Contents</A><br> <LI> <A HREF="../../ORMS.shtml" TARGET="_top"><I>OR/MS Today</I> Home Page</A><br>  <img src="../cleardot.gif" width=1 height=1 vspace=8 border=0><br> <img src="../barblue.gif" width=468 height=1 border=0 alt=" "><br> <b><i>OR/MS Today</i></b> copyright � 2003 by <A HREF="http://www.informs.org/" target="_new">the Institute for Operations Research and the Management Sciences</a>. All rights reserved.<br> <img src="../cleardot.gif" width=1 height=1 vspace=3 border=0><br> <img src="../bargrey.gif" width=468 height=1 border=0 alt=" "><br> <b>Lionheart Publishing, Inc.</b><br> 506 Roswell Rd., Suite 220, Marietta, GA 30060 USA<br> Phone: 770-431-0867 | Fax: 770-432-6969<br> E-mail: <a href="mailto:lpi@lionhrtpub.com">lpi@lionhrtpub.com</a><br> URL: <A HREF="http://www.lionhrtpub.com" target="_top">http://www.lionhrtpub.com</A><br> <img src="../cleardot.gif" width=1 height=1 vspace=3 border=0><br> <img src="../bargrey.gif" width=468 height=1 border=0 alt=" "><br> Web Site � Copyright 2003 by Lionheart Publishing, Inc. All rights reserved. </td></tr></table> <img src="../cleardot.gif" width=1 height=1 vspace=2 border=0><br> </BODY>