These solvers really show that NP-hardness is no reason to give up. For example, they can solve surprisingly large Traveling Salesmen instances to proven optimality.
Sadly, the field is still mostly dominated by commercial solvers. There are a few open source ones but their performance is nowhere near the commercial ones which is kind of expected given the number of people working on them and the little funding they have. It is really a pity that the OR world hasn't embraced open source as much as ML world.
Anyone has a good literature review (or anything similar) on AI technics applied to ILP/constraints solver ?<p>I have seen a couple of result for specific domain ( like place and route ) but I am wondering how those new technics fair in more general settings
"Combining the computer hardware speed increase of 4,000 times with the solver software performance improvement of 5 million times, the total improvement from 1989 to 2024 is a factor of 20 billion times faster!"<p>No wonder people have started making jokes that programmers no longer know how to program! We can get away with a lot more now.
I wish they tried to solve the 1989 4x4 crossword puzzle optimization with a modern solver, but a small memory limit (~8MB) and perhaps a severely underclocked CPU to showcase the algorithm improvements.
So solvers are now much faster, but I haven't found a single hint in the article as to <i>how</i> they got faster (aside from the "more memory", "more CPU" aspect).<p>Was there a major theoretical development in the solver field that allowed this to happen ?<p>Or is it a bunch of tiny tuning heuristics ?<p>If so, how are those even possible given that the solver is supposed to be a generic tool applicable to a large class of problem ?<p>Are there problems whose structure fit a recognizable pattern where optimizations are possible ?<p>I confess to being left hanging by the article.
Thanks for your interest in our article about solver performance.<p>We've now posted a follow-up pair of articles where we attempt to compile crossword puzzles using a Mixed Integer Linear Program.<p>Let us know if you have any questions.<p><a href="https://www.solvermax.com/blog/crossword-milp-model-1" rel="nofollow">https://www.solvermax.com/blog/crossword-milp-model-1</a><p><a href="https://www.solvermax.com/blog/crossword-milp-model-2" rel="nofollow">https://www.solvermax.com/blog/crossword-milp-model-2</a>
1989: Odd that the superminicomputer that cost hundreds of thousands had 8MB RAM and managed 1 MIPS, while my Acorn Archimedes cost $2000 had 1MB (and you could get up to 4MB) and managed 8 MIPS.
I would side with their grain of salt until they have actually completed their promise to implement a crossword puzzle solver using integer programming.
I wish they put all this increased computer power to solve the real problems, rather than crossword puzzles :/ we may have lived in a 4 day working week already
Are there good reference books on solver implementations?<p>I tried diving into the subject using online references but found them lacking in context and explanations sometimes.
Yet more reasons to try more central planning rather than rely on analog markets. If it’s good enough for large Capitalist firms, it should be good enough for sectors of the economy.