Best open source Mixed Integer Optimization Solver [closed]

Question

I am using CPLEX for solving huge optimization models (more than 100k variables) now I'd like to see if I can find an open source alternative, I solve mixed integer problems (MILP) and CPLEX works great but it is very expensive if we want to scale so I really need to find an alternative or start writing our own ad-hoc optimization library (which will be painful)

Any suggestion/insight would be much appreciated

Soldierly

100k variables is a very huge problem! I think that you may focus on investigating more time in changing modelisation. Lpsolve and glpk don't support that amount of integer variables to be resolved in a reasonable time. – Rebbeccarebe

As always, the most useful questions get marked for a technicality.. see the bigger picture, this question adds a lot to the knowledge-base – Sclater

Answer 1

I personally found GLPK better (i.e. faster) than LP_SOLVE. It supports various file formats, and a further advantage is its library interface, which allows smooth integration with your application.

Source

Answer 2

Another endorsement for COIN-OR. We found that the linear optimiser component (Clp) was very strong, and the mixed integer component (Cbc) could be tuned quite well with some analysis. We compared with LP-Solve and GLPK.

For really tough problems, a commercial solver is the way to go.

Ge

Answer 3

Try the SCIP solver. I have used it for MILP problems with over 300K variables with good performance. Its MILP performance is much better than GLPK. Gurobi has also excellent performance for MILP problems (and typically better than SCIP (May 2011)), but it might be costly if you are not an academic user. Gurobi will use multicores to speed up the solver.

Kenyakenyatta

SCIP is unfortunately not open source software. – Taciturnity

Did you really have over 300k variables? How many of those had integer constraints? – Sedulity

@FalkHüffner: perhaps it didn't used to be, but as far as I can tell (10 years later...) it is now in fact open source... – Plagio

SCIP is still not open source software, since the license does not allow anyone who is not a member of an academic institution to use it, and even for academics, the license has requirements that would preclude it from being open source as commonly defined. – Taciturnity

Looks like SCIP is now finally open source, as of this commit: github.com/scipopt/scip/commit/… . They changed the license to Apache-2.0. – Muco

Answer 4

If I were you, I would try to use a multi-solver interface such as Osi (C++) or PuLP (python) so that you can write your code once, and test it with many solvers.

If the integer programs you are going to solve are huge, I would recommend python over C++, because you code will look cleaner and 99% of the time will be spent in the solver.

• https://projects.coin-or.org/Osi
• http://code.google.com/p/pulp-or/

If, on the contrary, the problems are small, then the time for copying the problems from python's memory to the solver (back and forth) is not to be neglected anymore: in that case you may experiment some noticeable performance improvements using a compiled language.

But if the problems are overwhelmingly enormous, then compiled languages are going to win again, because the memory footprint will be roughly divided by 2 (no copy of the problem in python).

Siskind

I previously used lp_solve, then switched to using pulp. By default it uses COIN-OR. To solve a MIP problem I had, with 200 decision variables, lp_solve took 55min, GLPK took and 67min, Coin-or took 0.2seconds. – Dagnah

Sorry for the revival but is the memory footprint true for all solver implementations? (e.g. even with a commercial solver like Gurobi?) That would be a huge drawback to using python. – Beatification

I believe so. All python implementations are acting as wrappers around the C library. So for each variable, you get a python variable that points to a C value = twice the memory needed. This is true for any wrapper language, so you will get the same exact issue with C++. If you want to minimize the memory used, you need to use plain C and build the problem matrix from there. I would not worry about it too much, though: the productivity you gain from using a good abstraction will allow you to test many more things, and lead to a better implementation. Only resort to pure C if you have no choice – Siskind

Answer 5

Have you tried lp_solve? There were also some other suggestions in the following questions, for Java:

• mathematical optimization library for Java —- free or open source recommendations?
• Linear Programming Tool/Libraries for Java

Ladida

Answer 6

I recommend checking out the COIN project. COIN OR

Many good solvers here, including ipOPT for nonlinear problems and a couple mixed integer solvers as well.

Pulsatile

Answer 7

Scip is not bad!

Teratology

SCIP is not an open source solver. – Lefthanded

it is now! since november 2022 – Recourse

Answer 8

Although this is maybe not what you want to hear, but there are light-years between the commercial solvers CPLEX and Gurobi on the one hand and open source solvers on the other hand.

Nevertheless you can be lucky and your model works fine with GLPK, Coin or the like, but in general open source solutions are way behind the commercial solvers. If it was different, no one would pay 12.000$ for a Gurobi license and even more for a CPLEX license.

In the past years I have seen many, many models that were just to difficult for the open source solvers. Believe me...

It's not so much a question of size, but of numeric difficulty.

Tarpeia

Can you tell something more on what type of models are too difficult for the open-source solvers? – Theodolite

We've been working for example with models for gas industry and gas distribution, and there were dozens of models that were just too difficult for open source solvers. Usually LP models are not the big problem, but when it comes to MIP models only commercial solvers do well. Usually our models had several ten-thousands of variables. But it is not so much a matter of size. – Tarpeia

I do not necessarily disagree with your comment, but there are some cases where opensource solvers work just as well as commercial ones. This is why I recommend going for multi-solver libraries. This way, you will be able to treat the solver as an engine and to switch the solver easily, and compare, even between commercial solvers. Do not lock yourself into a technology, and use generic frameworks! – Siskind

Answer 9

I am surprised that nobody has mentioned MIPCL (http://www.mipcl-cpp.appspot.com/index.html). This solver claims to be open source under LGPL license (source: http://www.mipcl-cpp.appspot.com/licence.html), thus it is also suitable to be used in non-open-source applications. But what is missing to be really open source is the source code of the solver itself.

Hans Mittelmann very recently (10 Sep 2017) did Mixed Integer Linear Programming Benchmark: http://plato.asu.edu/ftp/milpc.html (you might also be interested in looking at the overview page http://plato.asu.edu/bench.html or the slides of his talk: http://plato.asu.edu/talks/informs2017.pdf).

In the Mixed Integer Linear Programming Benchmark with 12 threads and a time limit of 2 hours MIPCL managed to solve 79 instances. Only the commercial solvers CPLEX, Gurobi and XPRESS managed to solve more under the given constraints (86 or 87 instances, respectively).

Also in terms of the chosen performance metric (again using 12 threads) MIPCL is faster than the benchmarked SCIP derivates (FSCIPC, FSCIPS) and the open source solver CBC. Again only the commercial solvers CPLEX, Gurobi and XPRESS outcompete MIPCL significantly in terms of performance.

Lefthanded

What ever happened to MIPCL ? The links are dead. – Chauvin

@Chauvin I don't know what happened to MIPCL, but the author of MIPCL is Nicolai Pisaruk. His LinkedIn page is by.linkedin.com/in/nicolai-pisaruk-93981916a Why don't you ask him and post his answer here: I am curious about the reason, too. :-) – Lefthanded

Answer 10

100k variables is a large problem. Many of the open-source libraries do not function well with that many variables. From what I've read lp_solve has only been tested for around 30k variables. Using the commercial system may be your only choice.

Aurelea

Answer 11

I have used DICOPT using the NEOS server (http://www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html) to solve large (approx 1k variables and 1k constraints) mixed integer non-linear programs and found it excellent.

For my problem DICOPT did much better than the other MINLP solvers listed on the neos server BARON/KNITRO/LINDO/SBB etc.

There are certain constraints to submitting jobs to NEOS and it is slightly cumbersome but the free access to a powerful commercial solver more than makes up for it.

Moretta

Answer 12

I'll add the following to the already excellent answers.

Whilst, as others have pointed out, commercial solvers are much faster and more capable than the free alternatives it's important to consider how much of an optimality gap you can accept. For large problems with many integer variables you may get much faster solve-times if you can accept 1% or even greater optimality gap (defaults tend to be around 0.01% or less).

Of course if you are solving a problem where 1% translates into millions of dollars this is not acceptable - hence the market for top-notch solvers. (Some comparisons of Gurobi to free solvers here)

I would agree with others that using a platform that generates solver-independent problem files (such as *.mps, *.lp files) is worthwhile as you can then try out other solvers. I'm using PuLP and am finding it, and the free COIN_CBC solver, excellent. Although limited for problems with many integer variables.

Kippy

Answer 13

Not open source, but if you have a Microsoft Academic Alliance license, the Microsoft Solver Foundation (MSF) enterprise edition is included. Gurobi is also free for academic purposes, I've used it in my thesis research.

Centillion

This product is end-of-life. – Convalescent