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]

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!