Parallel Multi-Start

[ccoffrin]

It might be more valuable to parrallize multiple starts of the NLP solver, rather than the tree search. Worth exploring.

[Wikunia]

Might be reasonable if the gap to the global optimal seems to be huge, right? Otherwise if the gap is 0 or small enough to the best known solution which turns out to be the case most of the time it doesn't help, right?
If that is the case it should be an option to switch between gap priority and speedup.

[ccoffrin]

If the problem is non-convex then the relaxation is only locally optimal. Even in the gap is 0, there may be another solution out there with a non-zero gap.

That said, in being practical you probably only want to run multi-start when you converge to local infeasibly, and maybe when you get an error.

[ccoffrin]

also when the relaxation is worse than the incumbent you might also want to do it, just to increase your confidence that you should fathom this node.

To cover both of these ideas there are probably two generic solver options, avoid-removing-feasible solutions, avoid-removing-optimal solutions. Which of these you want will depend on the application at hand.

[Wikunia]

Yes I think an option to customize it in any sense is quite reasonable for Juniper. Definitely restarting in infeasible nodes is reasonable and maybe for special cases where you have like 16 cores it might be even reasonable to split it into 8 parallel branch and bound and 8 for restarts as there is nearly no improvement from 8 to 16 cores anyway currently.

[ccoffrin]

Yup! I think how to best make use of multiple cores is a good open question for R&D.