Linear Programming: Software Survey

Thirteenth in a series of LP surveys highlights trends toward mobile computing, cloud computing and optimization.

By Robert Fourer

Linear Programming Software Surveys

This is the 13th in a series of surveys of biennial 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, quadratic and more general 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 form at www.lionhrtpub.com/ancill/lpsurvey2015.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 a combination of algorithmic methods designed to find solutions that are optimal (or reasonably close to optimal) 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.

Much of the software for linear programming is specialized either to modeling or to solving. Thus, solvers typically link to many modeling systems, and modeling systems link to many solvers. In some cases the two may be acquired as separate products and linked by the purchaser, but more commonly they are available bundled in various ways. 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 similarly offer bundles with modeling systems, while others focus on integrated systems that provide a modeling environment specifically for their own solvers.

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. Popular general-purpose programming languages and specialized math/stat languages are 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 LP software is available as binaries that are ready to run or to link into the user’s applications. Our table also identifies products that make their source code freely available under one of the recognized open source licenses; the largest number of these are available through the COIN-OR repository (www.coin-or.org). Open source is attractive in situations where budgets are tight, or where the greatest degree of flexibility is required, such as when new or customized algorithmic ideas are being investigated.

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. Some LP products also work as spreadsheet 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 more powerful and general spreadsheet optimizers.

Virtually all LP solvers accept input of 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 have proceeded only slowly.

Platforms

It is by now standard to provide support for all three of the most popular operating system platforms: Windows, Linux and MacOS. Several other Unix variants appear frequently among Other OSs (and indeed some LP systems support MacOS through its underlying Unix-based shell).

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, particularly the solution of the linear system that is central to interior-point LP methods and the exploration of the search tree that is fundamental to MIP solvers. Support for distributed memory, using multiple independent computers connected by a network, is now also quite common though it generally requires some additional work to set up.

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.

All of the listed commercial products offer a variety of free or highly reduced-cost offerings for academic research and educational use. Free options are full-featured but may be either size-limited or time-limited (with the possibility of renewal). 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.

Local installations remain the dominant mode of LP software application, but optimization in the cloud has become an established alternative. A still-growing roster of modeling systems and solvers is available for testing through the online NEOS Server (www.neos-server.org). As a free service, NEOS does not provide guarantees of confidentiality or performance, but it is appropriate for many projects and has been averaging more than 40,000 requests a month. Commercial cloud availability has also continued to expand, both for public cloud services and private compute servers. Offerings based on public services remain quite varied, 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 generalizations to LP 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 that most MIP solvers provide branch-and-cut, presolve and heuristic search features. In addition, many of the listed solvers provide some form of infeasibility analysis as an aid to model development.

LP systems also provide a variety of extensions that fall under the general heading of stochastic and robust 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.

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.

What’s Next?

The summaries of new features since the previous survey are the expected mix of new algorithms, faster performance, more general models and extended interfaces. If linear programming software is in your plans for the next two years, what larger trends should you expect to see?

  • Mobile computing. Look for versions that run on ARM processors and for features that help you build LPs into specialized apps for widespread deployment. Large-scale modeling and solving might still seem beyond the ability of phones and tablets – but the same was said about PCs at one time.
  • Cloud computing. Look for services that support NEOS-style optimization on demand, and more generally for platforms that support with equal convenience all phases of the optimization modeling lifecycle. Also expect to see cloud services become the “back ends” for those mobile apps that require extra computing power.
  • Optimization. Look for software packages to further emphasize general problem-solving ability over specific algorithmic features. Expect “optimization” to supplant older terms such as linear and mixed-integer programming in characterizing what these packages do. And expect software to do more of the work in reformulating problems and choosing algorithms to get the results that you’re looking for.

Click here to view the 2015 Linear Programming Survey

Robert Fourer (4er@ampl.com) is president of AMPL Optimization Inc. and professor emeritus of Industrial Engineering and Management Sciences at Northwestern University.