Question on HiGHS solver for large MILP problems

[wehuang16]

I tried to use the HiGHS solver to solve a large mixed integer linear programming (MILP) problem with many binary variables, but it took a bit long to solve, and the optimality gap stayed at around 10% - 20%. I then tried a different commercial solver to solve the same large MILP problem, and it solved successfully and relatively quickly. On the other hand, for smaller sized MILP problem, as well as large sized pure linear programming (LP) problem without any binary variables, both the HiGHS solver and the commercial solver solved the optimization problem quickly and successfully.

I did a quick online/ChatGPT search, and it says that for solving large MILP problems and optimizing for binary variables, compared to the HiGHS solver, those commercial solvers employ advanced branch-and-bound methods, dozens of cut families (Gomory, MIR, flow cover, clique, lift-and-project, etc.), sophisticated branching rules, strong primal heuristics, advanced pre-solve reductions, and dynamic cut/heuristic selection. This is potentially the reason why commercial solvers can solve large MILP problems more quickly.

My question is, do you know some reasons that the HiGHS solver potentially solve large MILP problems slowly? Do we have some open-source efforts on making the HiGHS solver more powerful on solving large MILP problem in order to catch up with the capabilities of other commercial solvers?

In case you would like to learn more details about my particular MILP problem, or other information I should provide, feel free to let me know!

[Opt-Mucca]

I believe your ChatGPT summary is a bit misleading. HiGHS does employ most "advanced" solver techniques and as a project is improving. That is, there is a very active (open-source) effort to improve the performance of HiGHS so that optimization problems can be solved more efficiently and at a larger scale without using commercial tools. That being said, there is naturally a gap between our current performance and that available from commercial solvers (one which we are trying to close but will always exist to some degree). The gap comes from lacking some algorithmic advancements (much of which is not public and or not well described), e.g., aggregation in separation and MILP parallelism, as well as plenty of code optimization, e.g., more efficient data structures for certain sub-tasks and memory reduction. There is no single silver bullet, and it's rather many changes that eek out a bit of performance all stacked on each other. Please share your instance if you're able to (with a short description if possible)! I'll look into it when I have time and see if it can be incorporated into testing.