Linear Programming Software Survey

LP-Survey-Binary-Data-26972385-Wavebreak-Media-Ltd

Linear Programming

By Robert Fourer

Fourteenth in a series of LP surveys focuses on characteristics that are valuable in choosing products.

This is the fourteenth 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 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 in the directory.

For this year’s survey, the questionnaire was revised to focus somewhat less on technical distinctions and more on characteristics that are valuable in choosing products to investigate further. 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/lpsurvey2017.shtml.

Products Covered

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 discrete variables and constraints of other kinds, 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.

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 environments mediate between human modelers and solvers, providing general and intuitive ways to express symbolic models, while 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 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 model 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. The 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 affiliated with the COIN-OR project (www.coin-or.org) and many are maintained in repositories at GitHub (www.github.com). Open source is attractive for 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. Some study may be necessary however to determine whether a desired combination of efficiency, convenience and support is currently available in open source LP software.

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 file 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 computing platforms: Windows, Linux and macOS. Several other Unix variants appear frequently among Other systems supported (and indeed some LP systems support macOS through its underlying Unix-based shell). Also, there is increasing availability to run directly in a web browser.

Solvers offering parallel 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 quite common though it requires some additional work to set up.

Pricing and Distribution

The table shows commercial single 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 other licenses of varied kinds. 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 academic offerings for research and educational use. Free options may be limited in problem size (demo versions) or in time of validity (trial versions); some are sufficiently unrestricted to permit long-term use on large-scale projects. Open-source packages are, of course, free to use, though a few carry restrictions on inclusion in commercial application software.

Local installations remain the dominant mode of LP software application, but optimization in the cloud or as a software service 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, for services provided by vendors such as Amazon as well as services provided by customers on their own computing facilities. Offerings range from simple NEOS-style submissions of individual optimization jobs to sophisticated interfaces managing dynamic server pools.

Problem Types

LP software packages have increasingly been extended to handle more than just linear problems. Piecewise-linear and positive semi-definite quadratic objectives and constraints, in continuous or integer variables, are a common extension; they can be solved by generalizations to LP methods, though not always as easily. Also, many products accept conic quadratic formulations, which 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.

The variety of specialized variable types and constraint types continues to increase. As a result, many logical conditions can be stated directly, bypassing challenging or error-prone reformulation in terms of auxiliary variables and constraints. Sometimes a direct statement of a logical condition permits faster solving as well.

Although this survey is focused on LP, quite a few of the listed products can also handle general convex and even general nonlinear objectives and constraints. The listing should not be considered exhaustive with respect to nonlinear solver packages, however.

Algorithms

LP solvers offer a choice of simplex and interior-point methods for continuous problems. MIP solvers incorporate sophisticated branch-and-cut frameworks to accommodate even quite difficult problems, often with help from local search heuristics and specialized problem-simplification routines. Solvers have also been extended with other algorithms of varied kinds, to improve their effectiveness or range of applicability.

Solver performance has steadily improved, from the first ORMS Today survey to the present one – but less from algorithmic breakthroughs than through an accumulation of ideas for reducing problem size, tightening bounds, finding better solutions and taking advantage of common problem structures. 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 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.

Nevertheless, solver performance remains highly problem-specific. For applications of any difficulty, it is advisable to benchmark several relevant solvers on sample problems of interest, rather than making a quick choice based on measures of average solver performance.

What’s Next?

Vendors’ summaries of new features since the previous survey are the expected mix of new algorithms, faster performance, more general models, and extended interfaces. Trends for the next two years seem likely to be a continuation of those seen previously:

  • Mobile computing. Look for versions that run on ARM processors, support REST services and help you build LPs into specialized apps for widespread deployment. Large-scale modeling and solving might yet 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” or “prescriptive analytics” 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.

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

Access the Directory here.