Linear Programming

This is the 15th in a series of biennial surveys of software for linear programming, dating back to 1990. Information has been gathered by means of a questionnaire sent by INFORMS to software vendors. Results and vendor contact information are summarized by product in a series of tables available online.

For this year’s survey, the questionnaire was revised to focus the technical questions more on linear and related problems; questions on multiple objective optimization and on deployment features were added. The ordering of topics below 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 online listing of LP products. To be added to the online listings and directory, complete and submit the survey questionnaire available at: https://www.surveymonkey.com/r/JPJPRNK. All listings are free. 

Products Covered

Products listed in this survey are concerned, at the least, with minimizing or maximizing linear objectives 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 also 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. Also, the listings exclude products that address only certain applications or formulations of LP, as these products are more properly evaluated in the context of other software categories.

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, 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 language.

Much of the software for linear programming is specialized either to modeling or 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 within application systems 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 can be called through APIs – application programming interfaces – for popular general-purpose programming languages and specialized math/stat languages. Some products also offer their own specialized deployment tools for application development.

As solver API 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 APIs, so that their advantages in developing and maintaining a model formulation can be made available to broader application software. It is possible to embed an entire modeling system, or a particular model or 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 compiled programs that are ready to run or to link into the user’s applications. The survey 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 and most are maintained in public repositories such as GitHub. 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 are particularly convenient for submitting bug reports and communicating benchmark problems. Modeling systems use much more general and efficient formats for communicating problem instances to solvers and retrieving results, but each has adopted its own format, and efforts at standardization have proceeded only slowly.

Platforms

It is now standard to provide support for all three of the most popular computing platforms: Windows, Linux and macOS. Among Other systems there is gradually increasing support for the ARM processors that power phones, tablets and small single-board computers such as the Raspberry Pi.

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 many purposes, notably for solving the linear system that is central to interior-point LP methods, and for exploring the search tree that is fundamental to MIP solvers. Support for distributed memory, using multiple independent computers connected by a network, is now also fairly common, though it requires greater effort to set up. 

Pricing and Distribution

The online survey results show commercial single license prices typically in the 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 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 some carry restrictions on inclusion in commercial application software.

Local installations remain the most widespread mode of LP software application, but optimization in the cloud or as a software service has become an established alternative. Many of the modeling systems and solvers in this survey are available for testing through the free online NEOS Server, which receives thousands of submissions each day, with daily peaks of more than 20,000. Commercial cloud-based optimization services have also continued to expand, hosted by vendors such as AWS and Azure, as well as by customers who provide their own computing networks. 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 of 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.

A variety of specialized constraint types permit frequently encountered conditions to be stated directly, when otherwise they would require challenging or error-prone reformulations to linear or quadratic constraints. Sometimes a direct statement of an if-then-else or all-different constraint condition permits faster solving as well.

Facilities for multiple objectives also allow for more direct formulations of common situations. Objectives may be traded off or sequentially optimized in order of priority. 

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 OR/MS Today survey to the present one – but less from the discovery of new algorithms 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; several 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.

Survey Results

For a directory of LP vendors, as well as the results from the 2019 survey of linear programming software – including side-by-side comparisons of LP packages – click here.