Best open source Mixed Integer Optimization Solver

问题:

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

回答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.

回答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.

回答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.

回答4:

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

回答5:

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.

回答6:

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).

回答7:

Scip is not bad!

回答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.

回答9:

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.

回答10:

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.

回答11:

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.

回答12:

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.

回答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.