5 ms·

>even the current interior point implementation in HiGHS can be unacceptably slow relative to Gurobi (60-100 times slower). Considering that even Gurobi require

by quanto 4y ago

>even the current interior point implementation in HiGHS can be unacceptably slow relative to Gurobi (60-100 times slower). Considering that even Gurobi requires a couple of days to solve huge practical problems illustrates that the use of current open source solvers is totally impractical. The aim of this proposal is to identify key solver enhancements in the short, medium and long term that will help to bridge the significant gap in performance between HiGHS and the major commercial solvers. It's a great need in the scientific community. Gurobi is the leading commercial solution with a strict license and a high price tag. As the proposed open-source project is only focused on linear programming (as opposed to a general nonlinear optimization), the goal may as well be achievable. Best wishes for the authors.

SparseRunner 4y ago
Thanks. Matching Gurobi is not feasible, but HiGHS wants those who depend on open-source solvers to be able to work with bigger models than is currently possible. Once HiGHS has a good interior point solver (for QP) - the main aim of this proposal - the vision is to develop a nonlinear programming solver.
- quanto 4y ago
  In your expert opinion, what is Gurobi's edge? The foundational mathematical formulation for solvers has been known for decades. I have read that Gurobi has many heuristics that statistically work well against real world problems. What are concrete technical challenges HiGHS needs to solve to bridge the gap with Gurobi? (my academic background is in numerical analysis/scientific computing but I didn't specialize in writing optimizers)
  - SparseRunner 4y ago
    For interior point the key is writing a multicore matrix decomposition code that exploits sparsity and the range of problem structure that is encountered. For MIP it's having techniques to exploit the many different problem features that occur and ensuring that they are used intelligently.

by quanto 4y ago

SparseRunner 4y ago

Thanks. Matching Gurobi is not feasible, but HiGHS wants those who depend on open-source solvers to be able to work with bigger models than is currently possible. Once HiGHS has a good interior point solver (for QP) - the main aim of this proposal - the vision is to develop a nonlinear programming solver.

quanto 4y ago
In your expert opinion, what is Gurobi's edge? The foundational mathematical formulation for solvers has been known for decades. I have read that Gurobi has many heuristics that statistically work well against real world problems. What are concrete technical challenges HiGHS needs to solve to bridge the gap with Gurobi? (my academic background is in numerical analysis/scientific computing but I didn't specialize in writing optimizers)
- SparseRunner 4y ago
  For interior point the key is writing a multicore matrix decomposition code that exploits sparsity and the range of problem structure that is encountered. For MIP it's having techniques to exploit the many different problem features that occur and ensuring that they are used intelligently.