Open-Source Mixed-Integer and Linear Programming Solvers and Software

Exploring Mixed-Integer and Linear Programming Solvers

We know there are a range of solvers, free and paid, to choose from. We also know that for some situations, a free solver might be all that you need. This article is designed to help you better understand your choices among free solvers, their relative performance, and some questions to ask yourself in deciding what type of solver is right for you.

Academics: We offer a free, full-featured Gurobi license for qualifying students, faculty, and staff. Visit our Academic page to learn more.

Common Free Mixed-Integer and Linear Programming Solvers

There are several open-source packages available for optimization. Two popular ones are GLPK and LP_Solve. The nice thing about these packages is that it’s easy to get started because you can download and install them immediately. But these packages are far behind the state of the art in optimization.

Open-Source Performance: Mixed-Integer and Linear Programming Comparisons

Performance is typically a crucial consideration when choosing a solver. To give a sense of the relative performance of the various solver options listed above, we’ve summarized the results of independent benchmark tests maintained by Hans Mittelmann at Arizona State.

If we look at performance on Mixed Integer Programming (MIP) models across a broad set of test models, the table below shows results along two key dimensions: a) was the solver able to solve the model, and b) how quickly was the model solved? As you can see from the results, performance varies widely across solvers.

Internally, when testing GLPK and LP Solve on over 2400 models (ones that Gurobi can solve in under 1000 seconds), one of the solvers failed in 63% of the test cases, while the other failed in about 72% of the test cases.

What does it mean to fail? Sometimes the free solvers simply reached the 1,002nd time limit before optimizing the problem. But in some cases, the solvers reported an incorrect solution or falsely concluded that the problem was infeasible.

People often assume that open-source packages are close to the performance of commercial products, figuring that the free solvers might be two times or maybe ten times slower than their commercial alternatives. The reality is that Gurobi can often be 10,000 times faster than open-source solvers.

Unfortunately, when people experience slow performance with free solvers, they often give up on optimization technology altogether.

Three Reasons to Choose a Free Solver

As you can see from the data above, free solvers tend to struggle with practical models, either failing to solve them at all or solving them relatively slowly. However, we don’t mean to give you the impression that free solvers are never the right choice. Below are a few scenarios where you may want to consider a free solver.

1. There is no approved budget

Often times, when a company is first looking at using an optimization solver in their business, there may not be an approved budget. Management may still be trying to determine the role optimization can play in planning and decision-making, and the team doing the work is still “getting their feet wet.”

2. You prefer to program in C or C++

Most free solvers are written in C or C++ and don’t offer other APIs. GLPK requires you to use C. Gurobi offers both C and C++ APIs, as well as a full range of other APIs, including Python.

3. The model(s) being solved are both small and relatively easy to solve

Free solvers tend to struggle with larger and more difficult models, but if a free solver is able to solve your problem now, and you are confident that your problem won’t become more difficult in the future, then a free solver could be a reasonable choice.

We want to stress that you should consider future growth in the model. We’ve seen many situations where free solvers worked well on a small prototype but were unable to handle the production model. This can cause a lot of rework that you may be able to avoid.

Before you make the choice to use a free solver, we suggest that you look at relative performance on models of similar size and complexity to those that you are likely to want to solve eventually. We are happy to assist if you like. We have a very large library of models and may be able to run a specific comparison.

Avoiding the “False Negative” Trap

One of the most important questions people tend to ask when they are first exploring solvers is if optimization is a fit for their business. We have seen cases where someone selected a free solver, tried building a model, and the solver just couldn’t handle the problem. As a result, they assumed their problem was just too complex to use optimization techniques.

Others find free solvers just too hard to use, given the solver didn’t support the programming language they preferred, they couldn’t get support, etc. The team then ends the project and moves on. This is unfortunate since, with the right tools and support, the project might have been a great success. If you find yourself in this situation, please contact us. We may be able to help steer you in the right direction so you get the results you need to support continuing with the project.

Should I Start with Open-Source Tools and Switch to a Commercial Tool Later?

It’s great that it’s easy to get started with open-source tools, but you should approach them with your eyes open. For example, if an open-source tool is unable to solve your model, you shouldn’t assume that your project is hopeless.

Additionally, a state-of-the-art commercial solver can save valuable development time in several ways. First, the interfaces in commercial solvers are typically more polished and advanced than those in open-source tools. For example, the Gurobi Python interface brings a modeling syntax to the popular Python language. Second, commercial systems like Gurobi offer pre-built IT infrastructure like client-server options and cloud computing.

Overview of Free vs. Commercial Solvers

There are several important differences between free and commercial solvers you should keep in mind:

Try Gurobi for Free

Sign up below for a free commercial evaluation or academic license. Then take Gurobi for a spin! You can even export and run your MPS files and experience the difference for yourself.