71–80 of 84 posts
Are there good reference books on solver implementations? I tried diving into the subject using online references but found them lacking in context and explanations sometimes.
For mixed integer programming solvers, this thesis is a good reference: https://opus4.kobv.de/opus4-zib/frontdoor/deliver/index/docI...
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.
Earlier quoted context omitted.
Optimal is overblown for business problems in general. Knowing there’s a mathematically optimal solution, people want it. Even if it’s practically impossible to get. It feels like if you have the optimal, you don’t have to consider trade offs (not usually true). Having a solution within 1% of optimal with ten nines of confidence is usually indistinguishable. Anyone ever notice how these CS problems are rarely famous…
I'm quite convinced that if you had a 1% better solution to the salesman problem than what fedex or ups currently have, they'll pay good money, though :)
What's the point of the theoretically perfect solution when the travel times are so unpredictable? The truck stops are 3-5 minutes apart on average (according to random reddit comment [0]), 1% of that is 3 seconds. Meanwhile a single missed light (say because some other vehicle was driving slow or UPS driver was guided into non-familiar route) can add more than a minute.
So something like a better way to arrange packages in truck, or better traffic preidiction model, would be much more useful than any TSP improvements.
[0] https://www.reddit.com/r/UPS/comments/89zw0h/how_long_does_o...
Earlier quoted context omitted.
Optimal is overblown for business problems in general. Knowing there’s a mathematically optimal solution, people want it. Even if it’s practically impossible to get. It feels like if you have the optimal, you don’t have to consider trade offs (not usually true). Having a solution within 1% of optimal with ten nines of confidence is usually indistinguishable. Anyone ever notice how these CS problems are rarely famous…
I'm quite convinced that if you had a 1% better solution to the salesman problem than what fedex or ups currently have, they'll pay good money, though :)
We've now posted a follow-up pair of articles where we attempt to compile crossword puzzles using a Mixed Integer Linear Program.
Let us know if you have any questions.
Earlier quoted context omitted.
The software improvements are on an order of 1000x more than the hardware improvements. IE: The software matters more. As in, today's programmers know more about this subject.
I'd say that the algorithm matters more. As in, today's mathematicians know more about the subject. I suspect the actual implementation of said algorithms probably achieves a lower % of peak performance than the older ones (though to be fair they are /much/ more complex algorithms).
In my experience I have found the opposite to be the case. Most old maths libraries are written in FORTRAN (generally an order of magnitude or more slower than a comparable C/C++) and the implementations of standard algorithms are often sub-optimal and naive. I got the same impression when I compared arctangent (Taylor series) implementations in π programs and Minimax in chess (see Bernstein's program for the 704). I would guess that in the worst case they were 100x slower than what those machines could theoretically achieve. The C+inline asm libraries of today might be 2-10x slower at worst and some are even bottlenecked by memory. In this case I doubt the programs discussed in the 1989 paper, which were written in Prolog and FORTRAN, are exceptions to this.
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.
Earlier quoted context omitted.
I'm quite convinced that if you had a 1% better solution to the salesman problem than what fedex or ups currently have, they'll pay good money, though :)
I would not be so sure. What's the point of the theoretically perfect solution when the travel times are so unpredictable? The truck stops are 3-5 minutes apart on average (according to random reddit comment [0]), 1% of that is 3 seconds. Meanwhile a single missed light (say because some other vehicle was driving slow or UPS driver was guided into non-familiar route) can add more than a minute. So something like a be…
I would side with their grain of salt until they have actually completed their promise to implement a crossword puzzle solver using integer programming.
https://www.solvermax.com/blog/crossword-milp-model-1
https://www.solvermax.com/blog/crossword-milp-model-2
Though note that we're compiling new crosswords, rather than solving existing puzzles.