Re:Researchers have found a faster way to do integer linear ...
by nkh on Monday January 29, 2024 @11:11PM
(#39186333)
All these solvers use branch and bound to explore the solution space and "fathom" (i.e. eliminate candidate search trees if the lowest possible value for the tree is above an already found solution). The upper bound that the solver calculates via pre-solve heuristics and other techniques does vary from solver to solver. However, they all have a place for "Upper bound", and there are mechanisms in all of these solvers for updating that value in a current solve.
If this paper were a complementally orthogonal implementation from everything that exists in these solvers today, if it can produce a new upper bound, faster than other techniques, it should be fairly plug and play.
I have an undergrad OR degree, and I have been a practitioner for 18 years in LP/MIP problems. So I understand the current capacities of these solvers, and have familiarity with these problems. However, I and am out of my depth trying to understand the specifics of this paper, and would love to be corrected where I am missing something.
Re:Researchers have found a faster way to do integer linear ...
by Aaronmacaron on Tuesday January 30, 2024 @03:23AM
(#39187619)
What is OR?
Re:Researchers have found a faster way to do integer linear ...
by aix1 on Tuesday January 30, 2024 @03:27AM
(#39187659)
Operations Research: https://en.m.wikipedia.org/wiki/Operations_research
Re:Researchers have found a faster way to do integer linear ...
by soperj on Monday January 29, 2024 @10:43PM
(#39186163)
Wouldn't the "open source ones like SCIP for the small ones." be public by design?
Re:Researchers have found a faster way to do integer linear ...
by mulmboy on Tuesday January 30, 2024 @01:59AM
(#39187155)
In many cases you can actually insert outside numbers in the middle of the solver process via callbacks. For example see IncumbentUpdater at https://python-mip.readthedocs.io/en/latest/classes.html
And various C APIs for solvers have other callbacks
It's generally quite limited of course, for the reasons you mentioned.
Re:Researchers have found a faster way to do integer linear ...
by 7thaccount on Tuesday January 30, 2024 @03:16AM
(#39187572)
The math programming languages of AMPL, AIMMS, GAMS...etc are dying in my industry and being replaced by general industry languages like Python/Java + Solver API.
However, the solution is something very specific to the individual solver and they have their own data structures, algorithms and heuristic techniques to solve the problem. None of these are interchangeable or public (by design) and you cannot just insert some outside numbers in the middle of the solver process without being part of the solver code and having knowledge of the entire process.