MIP solver plans and roadmap

[douglaswaynepotter]

Hi,

Thanks for upping the open source solver diversity!

I couldn't find any plans or roadmap concerning the MIP solver. If there is such a doc, please let me know the link. I am particularly interested in parallelization and other performance plans.

Thanks.

[sschnug]

Interesting question.

Observing the project for quite some time now (even before it was named HiGHS), i was pretty enthusiastic when MILP development began and i was amazed how quickly it became very (!) competitive, even compared to pretty advanced solvers like SCIP (which imho is a big source of inspiration for the current design).

I thought it would become the leading open-source MILP solver potentially attracting more external contributors.
There are some nice aspects to the project for contribution. Although subjective, the things i evaluated positively are:

• the project is not too big and the code is quite readable (compared to Cbc+SCIP)
• it has modern build-tooling (compared to Cbc)
• it's C++ based (compared to SCIP which is C)

Some fears emerged when i recognized, that the MILP parts are basically only developed by a single developer (Leona Gottwald), which renders things very fragile. CoinOR Cbc is not much different there i would argue (which might lead to things like no OSI support for many years).

I think, that contributions to the core have been minimal, potentially due to having no roadmap / planning and contribution guidelines (like: "we miss that"; "that would be a good start to contribute", ...). Maybe there are other reasons too (i did not like the source documentation when i tried to add some primal-heuristic and needed to reverse-engineer basic memory-layout questions...).

Then, without trying to take anything away from the project (it's still awesome), two things happened (during the last few months) which might change a lot for HiGHS' future (personal opinion!):

• SCIP got a weak copyleft license allowing much more people to use it commercially

  • It was always a great solver with great documentation and is still actively maintained and now the license situation got so much better!
  • Yes... HiGHS beat SCIP in benchmarks which surprised me and speaks for the talent behing HiGHS development, but i somewhat question future improvements there while i'm sure SCIP will evolve (see next point)

• Leona Gottwald seems to be part of FICO now (company behind the commercial solver Xpress) and there is a clear correlation of this affliation and her public github activity (basically empty since then)

So yes... i would be interested to know, if there is even a MILP developer left.

LP development and (open-source) maintainment work looks good (although even there one can recognize the "one person clusters"). MILP... not so much.

Obviously, i hope i'm wrong and my fears are unfounded :-(.

[douglaswaynepotter]

As far as I understand, HiGHS does not welcome (outside) contributions to core algorithms.

[jajhall]

So yes... i would be interested to know, if there is even a MILP developer left.

LP development and (open-source) maintainment work looks good (although even there one can recognize the "one person clusters"). MILP... not so much.

Obviously, i hope i'm wrong and my fears are unfounded :-(.

A lot has happened since you expressed your (reasonable) doubts three years ago. The HiGHS team is now eight-strong, wit three people working on MIP. It's been a big learning curve for them, but we now have a prototype multi-threaded solver. Although it's logically correct, it still needs a lot of tuning. Hopefully it'll be released by June. We also have promising work on primal solution generation, and continued work on MIP presolve.

We've got a new multi-threaded interior point solver for LP, that has been extended to convex QP, and will be released in a matter of days

[sk-surya]

@jajhall, Do you think the release by June is still feasible for the multi-threaded MIP solver? Excited for it.

[jajhall]

Yes, the parallel MIP solver is (slightly hidden 😁) in #2886, which is soon to be merged, and we'll create v1.15 by the end of May.

[jajhall]

Thanks @sschnug and @douglaswaynepotter , what you say is largely correct.

We don't currently have a MIP developer so, since many aspects of the HiGHS codebase are mature, and we've recruited to push new developments in continuous optimization, I'll take over support for the MIP solver, and implement the improvements that Leona left in the pipeline. One of these is parallelization of the search, something that will significantly enhance the solver performance. This and concurrent solution of MIP root nodes - deterministic race between simplex variants and the barrier solver - will take the performance of the HiGHS MIP solver even further ahead of SCIP than it is now. [I don't count the SCIP+CPLEX results, as that's not open-source]. Although you suggest that SCIP will evolve, I'd be surprised if true open-source SCIP ever approaches the performance of HiGHS in future. We'll also add features like call-backs for cut definition.

So, although major MIP development work isn't foreseen at present, there's no great drive to improve performance so long as what we have remains the world's best open-source MIP solver. Indeed, if we find ourselves in a position to develop the MIP solver significantly, there are thoughts of creating a premium paid-for version of HiGHS to help fund the whole project.

I think the comparison of HiGHS and Cbc is a bit unfair, as HiGHS isn't a one-person project and, as you say, the HiGHS source is very much more readable. Specifically, Ivet is employed by the School of Maths, which wants to capitalise on what we've achieved, and we have significant donated funds - about 30 times what COIN-OR has! - for further development in the next 2-4 years. I'm also significantly younger than JF!

I know that HiGHS is severely lacking in documentation, but plans for that are in hand now that we have highspy. We will document the Python API, which is very similar to the C++ API, leaving C++ and C programmers to use the Python documentation and documented C/C++ header files.

As for outside contributions to core solvers it's true that we don't encourage them, particularly in areas where there's a developer in the HiGHS team. This is because it's hard to see someone being able to make contributions that are worth the disruption and risk involved. The MIP solver is another issue now that we don't have a developer. There's still the risk of code being developed that isn't supported: at least at the moment all the unsupported code was written by one person. I'd be open to a discussion if someone very skilled wanted to contribute.

Sorry for not replying sooner. I keep forgetting to check on discussions since I focus on issues!

[ExpandingMan]

I'm curious if there are any updates on this and if this old post still reflects the current status.

In my experience HiGHS is good enough at solving real relaxations that it could probably replace commercial solvers in a lot of real use cases. For example, for some very large problems I work on the HiGHS relaxation usually only takes around 3 to 5 times as long as the Gurobi one, which considering the cost of Gurobi, is pretty damn good. However, branch and bound is much further behind and even allowing for a time budget ~ 10 times that of gurobi, it's certainly not there yet. I'm curious if there are currently plans to work on MIP's.

Anyway, thanks to all the developers for the great work on this software!

[jajhall]

However, branch and bound is much further behind and even allowing for a time budget ~ 10 times that of gurobi, it's certainly not there yet. I'm curious if there are currently plans to work on MIPs.

We've had hopes/plans for a couple of years, but we've had a developer working on multi-threading the MIP solver since May last year, and we now have a prototype solver. Although it's logically correct, it still needs a lot of tuning. Hopefully it'll be released by June.

[ExpandingMan]

That's great to hear! Appreciation for all the hard work!

[S-sa-199]

This is great news. I have used HiGHS to solve pretty large MILPs with good results. However I am curious if you have an estimate of the expected speedup afforded by a multithreaded MIP solver.
I have tested the performance scaling vs. number of cores with commercial solvers and, at least on my problems, you get a somewhat linear speedup up to 2-3 cores, maybe 4, on some instances. But no more. And on some instances I saw no gain at all between N=1 core and N>1. So, parallelism alone is not enough to justify the typical performance differential observed between the best OS solvers (i.e. HiGHS) vs. the best commercial solvers.

This aligns with my expectations because it is a very well-known fact that branch-and-bound style algorithms are very weakly parallelizable. Therefore, I expect that for large, hard MILP problems, a multi-threaded MIP solver could yield something in the ballpark of a 2x-3x speedup, if the scaling properties match those of commercial solvers . Am I on the right track ?

Thank you very much for all the good work !

[jajhall]

Since we're behind the commercial solvers on serial performance, our multithreaded tree search (and multithreaded primal heuristics) may have a greater impact. The author of the HiGHS MIP solver estimated that we'd get 3-5 times speed-up on amenable problems with the parallelization scheme she designed (but didn't implement).

So, parallelism won't close the gap to the commercial solvers, but a 4x speed-up will make a decent difference.

In passing, we're also going to start using the interior point solver for the root node LP if it looks advantageous. For some MIPs HiGHS is prohibitively slow because simplex is too slow on this LP.

We'll never catch up with the commercial solvers on MIP, but aim to be good enough for an increasingly large number of users. And we'll always be infinitely cheaper! 😅