5 ms·

Constraint solvers are indeed powerful tools, but 8M cases is just not that many. I don't have a python terminal handy, but I suspect that a brute-force triple

by klyrs 5y ago

Constraint solvers are indeed powerful tools, but 8M cases is just not that many. I don't have a python terminal handy, but I suspect that a brute-force triple for-loop wouldn't take more than a second.

djtriptych 5y ago
Had the same thought reading the title. If N = 8000000 and I only need the answer once, I'd definitely just brute force and like... count to ten.
- dragontamer 5y ago
  Modern CPUs are 4GHz processors. If you need 100 clock cycles per brute-force check, you can brute-force 40 million cases per second. 8-million is actually very small. Modern computers (GPUs really) are on the order of reasonably brute-forcing 2^40-ish search spaces these days (or one-in-a-quadrillion, depending on the complexity per check) ~1GHz clock on GPUs x 4096 shaders == 4-trillion gpu-shader core cycles per second. If you're willing to wait 1-hour (3600 seconds), that's 14-quadrillion gpu-shader clock cycles.
  - charcircuit 5y ago
    Don't forget that modern cpus have multiple cores so that's another 8 or 16 times speedup.
deathanatos 5y ago
So the first part one only has 10k cases, and takes 542µs for Python on my laptop to find the two solutions that exist. (There's the 9,139 soldiers in the article, but "the enemy camp was abandoned", i.e., 0¹ also fits the given constraints.) Part II only takes 73 µs for the small example, and 6.77s for the large one (the one in the title). ¹ah, I re-read the article and "The lower bound is 1 since we know there's an army" … but that's not ever established in the math parts. Do we know there's an army? Our scouts seem … eccentric. Of course, while the prose claims a lower bound, the math immediately below that paragraph contradicts it with "0 ≤ army ≤ 10000"… (given the waffling in the article on this bound, I suspect the author's initial implementation of a constraint solver probably returned 0, at which point they updates some parts of the article…)
- tgv 5y ago
  The first case consists of counts that are relative primes, so it's a multiple of the product. No need for code, just a hand-held calculator, but that's not the point of the post, of course.
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 ago
  Sure, 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.

by klyrs 5y ago

djtriptych 5y ago

Had the same thought reading the title. If N = 8000000 and I only need the answer once, I'd definitely just brute force and like... count to ten.

dragontamer 5y ago
Modern CPUs are 4GHz processors. If you need 100 clock cycles per brute-force check, you can brute-force 40 million cases per second. 8-million is actually very small. Modern computers (GPUs really) are on the order of reasonably brute-forcing 2^40-ish search spaces these days (or one-in-a-quadrillion, depending on the complexity per check) ~1GHz clock on GPUs x 4096 shaders == 4-trillion gpu-shader core cycles per second. If you're willing to wait 1-hour (3600 seconds), that's 14-quadrillion gpu-shader clock cycles.
- charcircuit 5y ago
  Don't forget that modern cpus have multiple cores so that's another 8 or 16 times speedup.

deathanatos 5y ago

So the first part one only has 10k cases, and takes 542µs for Python on my laptop to find the two solutions that exist. (There's the 9,139 soldiers in the article, but "the enemy camp was abandoned", i.e., 0¹ also fits the given constraints.) Part II only takes 73 µs for the small example, and 6.77s for the large one (the one in the title). ¹ah, I re-read the article and "The lower bound is 1 since we know there's an army" … but that's not ever established in the math parts. Do we know there's an army? Our scouts seem … eccentric. Of course, while the prose claims a lower bound, the math immediately below that paragraph contradicts it with "0 ≤ army ≤ 10000"… (given the waffling in the article on this bound, I suspect the author's initial implementation of a constraint solver probably returned 0, at which point they updates some parts of the article…)

tgv 5y ago
The first case consists of counts that are relative primes, so it's a multiple of the product. No need for code, just a hand-held calculator, but that's not the point of the post, of course.

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 ago
Sure, 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.