Do we know why open source MIP solvers are significantly slower than commercial ones?

[SanPen]

I develop power system software, and part of that involves solving large MIPs.

While testing different solvers, I noticed that the open source ones (Highs, CBC, Scip) perform about the same, while the commercial ones (CPLEX, XPRESS, and Gurobi) perform about the same among them, but are about two orders of magnitude faster than the open source ones for the same MIP, sometimes yielding different solutions that also solve the problem.

This seems to be due to an algorithmic advantage rather than to programming techniques.

¿Do we know what commercial solvers are doing to be much faster?

I've noticed that for LP problems of the kind that I solve, all solvers perform comparably.

[jajhall]

Commercial MIP solvers benefit from person-decades of development investment - funded by high license fees. They have parallel tree search, and all sorts of tricks to handle different classes of problem. You may have seen "two orders of magnitude" difference in performance on your instances, but it's about one order of magnitude for Mittlemann's benchmarks between HiGHS and Gurobi - and not much more for SCIP and Cbc. HiGHS is looking to parallelise its tree search in 2024.

Again YMMV, but for LP on Mittlemann's benchmarks the best open-source solver - HiGHS - is 20 times slower than the best commercial solver (COPT). That's down to the idiosyncratic IPM implementation in HiGHS - which is why it's better than other open-source LP solvers - and parallelism. HiGHS is writing a new solver with the aim of reducing the gap.

[timellemeet]

Was a typo. Yes fully understand! Happy to help test some real world cases when we get there. I do column generation and solve the subproblems already on a GPU (using JAX). So it would be the ideal application I think. We are running many larger and smaller "jobs" each day by now in production, all powered by HiGHS and JAX. Happy to tell you more about if manage to make it to the workshop in June.

[jajhall]

Sounds exotic. It would be interesting to have you present your work at the workshop

[kutlay]

@timellemeet This sounds very exciting, is there any demo/presentation anywhere? Are you planning to pursue this as an open source project?

[raulhuatuco]

Was a typo. Yes fully understand! Happy to help test some real world cases when we get there. I do column generation and solve the subproblems already on a GPU (using JAX). So it would be the ideal application I think. We are running many larger and smaller "jobs" each day by now in production, all powered by HiGHS and JAX. Happy to tell you more about if manage to make it to the workshop in June.

sound interesting

[sk-surya]

@timellemeet, very interesting approach. I thought the cuPDLP-C works best for very large LPs, never thought of using it to solve many many small subproblems parallelly. How many subproblems are you solving at the same time? And what's the speedup you get when compared to solving the subproblems using CPU?