2 ms·
There's 8 million solutions to the constraint 1000 ≥ Bread×1 + Meat×3 + Beer×7. a brute force triple loop would check a bunch of possibilities that aren't solu
by Avshalom 5y ago
There's 8 million solutions to the constraint 1000 ≥ Bread×1 + Meat×3 + Beer×7.
a brute force triple loop would check a bunch of possibilities that aren't solutions either the very naive 1000×1000×1000 (for one billion) or slightly less naive 1000×333×142 (for 47.3 million).
Not that a billion would take that long either on a modern computer, but if you look at the OR-Tools solution, it's really not any longer or more complicated than loops would be. As long as you have good tools (coughprologcough) it doesn't take very long for constraint solving to come just as naturally as loops.
- klyrs 5y agoSure, sure. I wasn't at a computer at the time and didn't pay the closest attention to the problem. Turns out that the brute-force solution involves two for-loops, not three, because you'd be a fool if you don't make bread the innermost loop and optimize it away by filling the remaining capacity. So the N=1k takes about 6.5ms on my desktop, and the N=10k takes a mere 400ms. Only when I try 100k do I need to actually wait, for an egregious 40s. And, a more trifling note, their variable bounds are too generous... meat = model.NewIntVar(0, 1 + capacity // 3, 'meat') beer = model.NewIntVar(0, 1 + capacity // 7, 'beer') reduces the triple-loop estimate to a mere 47M cases.