Hacker News new | ask | show | jobs
by nullc 654 days ago
Are you aware of any survey papers on some of the strategies used by (near) state of the art solvers?
2 comments

Not the same person but maybe "Mixed-Integer Nonlinear Programming: A Survey of Algorithms and Applications" could be a good start? I haven't read it yet.

HiGHS is the best open source MILP solver at the moment, and MATLAB of all things has a pretty good explanation of how it works internally: https://nl.mathworks.com/help/optim/ug/mixed-integer-linear-...

I am an academic in the field. A good starting point would be Tobias Achterberg's PhD thesis:

"Constraint Integer Programming"

It details the implementation of SCIP, which is one of the leading open source solvers, and explains some of the most important tricks.

That said, there is a lot of literature out there; if you're interested in a particular aspect like e.g. presolving or cutting planes, then feel free to ask me further questions. It is worth noting that the implementation specifics are hidden by the top commercial solvers, so these are difficult to find anywhere

thank you very much!

when i investigated the situation five years ago in https://dercuano.github.io/notes/linear-optimization-landsca..., scip was not open source, though zimpl was. looking at https://github.com/scipopt/scip?tab=License-1-ov-file#readme, it appears that scip has become open-source since then, which is very welcome news!

how does highs compare to scip?