Linear Programming Software Survey

Twelfth in a series of LP surveys highlights new features, facilities that help address a broader variety of applications.

Linear Programming Software Survey

By Robert Fourer

This is the twelfth in a series of OR/MS Today 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 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 online version of the survey listing. To learn more, write to Online Projects Manager Patton McGinley, patton@lionhrtpub.com, or go directly to the survey at www.lionhrtpub.com/ancill/lpsurvey2013.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 latter 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 as callable programs, generally in the form of class libraries in an object-oriented framework. About half a dozen general programming languages of varying designs are widely supported for this purpose; some products also offer their own specialized application development tools.

Solver systems have long been available as program libraries, allowing them to be embedded within application-specific systems and interfaces. As solver library designs have evolved, some have taken on aspects of symbolic modeling, such as algebraic specification of constraints. At the same time, modeling systems have been extended to offer their own program libraries, 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 numerous solvers that make their source code freely available under one of the standard open source licenses; many of these are available through the COIN-OR repository (www.coin-or.org). Open source is ideal in situations where budgets are tight or where the greatest degree of flexibility is required, such as in creating new algorithms and algorithmic schemes. Many of the open-source solvers are also available as precompiled 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 optimizers. 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.

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, but each has adopted its own format, and efforts at standardization are still at an early stage.

Platforms

Among operating system platforms, Windows remains ubiquitous, while Linux and MacOS are very widely supported as well. Several other Unix variants appear frequently among Other OSs (and indeed many LP systems support MacOS through its underlying Unix-based shell). Several products offer tools to help modelers create Web-based applications; app development tools for tablets or phones seem a likely next step, but none seem to be in release as yet.

Solvers offering multiprocessor versions for shared memory have become common, as the number of cores available in off-the-shelf PCs continues to increase. Indeed the automatic use of all available cores has become routine for some purposes, such as the exploration of search trees in MIP solvers. Support for distributed memory remains relatively less common, perhaps due to the greater difficulty in achieving a favorable cost-performance tradeoff while supporting a diversity of high-end computing architectures.

Essentially all LP software packages now take full advantage of available memory (using 64-bit processors), as well as available disk space where appropriate.

Pricing and Distribution

The table shows single commercial licenses running from hundreds to thousands of dollars, but as most vendors have a considerable range of license types and pricing arrangements, it is advisable to get a quote or consult a complete price sheet before arriving at any conclusions about costs. The most popular MIP solvers do tend to be at the high end of the price range. 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.

For educational purposes and academic research, an increasing number of full-featured commercial systems are available free under reasonable conditions. Free size-limited student (or demo) versions are also available for experimentation with small problem instances; several modeling systems offer conveniently packaged demo versions with one or more solvers.

Where free versions are not available, both modeling language and solver developers will arrange to provide full versions of their software for testing for a limited time. Of course, open-source packages are free for any use.

Convenient Remote Access or Cloud services are increasingly an alternative to local installations of optimization software. Many modeling systems and solvers have long been available for testing by submission through the Internet to the NEOS Server (www.neos-server.org). As a free service, NEOS does not guarantee confidentiality or performance, but it is appropriate for many projects and has been averaging more than 35,000 requests a month. Commercial cloud availability has expanded considerably since the last survey, using Amazon EC2 and other cloud platforms. Services are quite varied at this stage, ranging from creation of virtual machines with pre-installed optimization software to acceptance of NEOS-style submissions of individual optimization jobs.

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 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 the related but distinct realm of constraint programming software. The distance between integer and constraint programming is thus slowly narrowing, though it will not likely disappear anytime soon.

Convex quadratic objectives and constraints, in continuous or integer variables, are another popular extension; they can be solved by extensions to LP interior-point and branch-and-bound methods, though not always as easily. At the least, this category includes the classic positive semidefinite quadratic formulations that describe elliptical regions. An increasing number of solvers also accept conic quadratic formulations that specify various cone-shaped convex regions. These latter are particularly versatile because a variety of non-quadratic and even non-convex function classes admit translations to them, thus extending the range of applications that can be addressed.

Although this survey is focused on LP, quite a few of the listed products can also handle general convex, general nonlinear and other constraint types including complementarity, semidefinite, logical and chance constraints. The listing should not be considered exhaustive with respect to these types, however, as other kinds of high-quality solvers can be applied to them as well.

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 table records MIP solvers that provide branch-and-cut, pre-solve and heuristic search features, all of which have become quite standard. Also many of those listed provide some form of infeasibility analysis as an aid to model development.

Much of the improvement to MIP solvers has come through an accumulation of ideas for reducing problem size, tightening bounds and finding better solutions. Inevitably this has led to very long option lists; close attention to solver documentation can suggest which option settings might improve performance on a particular problem, but often only a fraction of the possibilities can be tested. Thus an important aspect of any MIP solver is its choice of default settings that adapt to characteristics of the problem at hand; a few solvers also provide automated “tuning” features that can suggest to the user which options to set. For difficult problems some careful benchmarking is ultimately necessary to make a reasoned choice among solvers and options.

Prominent in the list of other algorithms are 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.

What’s New

Among the reported new features since the previous survey, purely algorithmic enhancements are a minority. Many new features involve more convenient or extensive interfacing to other systems and environments. Also common are new facilities that allow algorithms to take advantage of more powerful computer and network architectures, notably multiprocessor and cloud environments as mentioned earlier. Finally there is evidence of a broadening of systems to recognize and efficiently handle additional problem types and structures, thereby permitting an individual modeling system or solver to address a broader variety of applications.

Robert Fourer (rfourer@4er.org), professor emeritus of Industrial Engineering and Management Sciences at Northwestern University and president of AMPL Optimization Inc., 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.