News for hackers. Stuff that matters.

A comment on Researchers have found a faster way to do integer linear programming. Parent comment

Re:Researchers have found a faster way to do integer linear ... by FwarkALark on Monday January 29, 2024 @11:04PM (#39186282)
> If would likely take significant research effort to even figure out a way to incorporate the new discoveries into these engines.

What? Have you ever used a solver before? The actual APIs exposed to the user are very simple interfaces that should allow swapping out the backend regardless of the complexity. The idea a new algorithm—short of something like "updating the solution to adjust to a change in data"—would not require any sort of research to slot in as an implementation for the existing interface.

[ Parent | on HN ]
Re:Researchers have found a faster way to do integer linear ... by adgjlsfhk1 on Monday January 29, 2024 @11:18PM (#39186358)
the interface is simple, but modern solvers apply a ton of heuristics that often dramatically reduce problem size, so a naive implementation of a better algorithm that isn't hooked deeply into the core of an existing ilp solver is likely to be very slow
[ Parent | on HN ]
Re:Researchers have found a faster way to do integer linear ... by FwarkALark on Tuesday January 30, 2024 @01:48AM (#39187098)
Why is this exposed to the user? If it isn't exposed to the user, what on earth are you talking about?
[ Parent | on HN ]
Re:Researchers have found a faster way to do integer linear ... by 7thaccount on Tuesday January 30, 2024 @03:13AM (#39187562)
Why would the API expose the heuristics to the user? Because an intelligent user can make minor adjustments and turn certain features on/off to sometimes dramatically increase performance depending on the problem.
[ Parent | on HN ]
Re:Researchers have found a faster way to do integer linear ... by rocqua on Tuesday January 30, 2024 @02:03AM (#39187188)
From what I gather the parent post is saying that it is easy to make a naive implementation of this improvement, but due to naivety of the implementation it will be slower in practice. Hence it is a lot of work (and thus difficult) to actually put this improvement into practice.
[ Parent | on HN ]
Re:Researchers have found a faster way to do integer linear ... by pmart123 on Tuesday January 30, 2024 @11:35AM (#39192131)
The api interface is simple, but the change would impact the code underneath. Since these are branch and bound algorithms, it would really depend on how often the worst runtime complexity case occurred. If it only happened in 2% of use cases, it might not make a huge difference for example.
[ Parent | on HN ]