Re:A CP Solution for XKCD NP Complete Restaurant Order
by swannodette on Tuesday May 28, 2013 @01:42PM
(#5781361)
Wow I did not know that Excel ships with a constraint solver and has since 1991 - http://www.utexas.edu/courses/lasdon/design3.htm
[ Parent
| on HN ]
Re:A CP Solution for XKCD NP Complete Restaurant Order
by mistermcgruff on Tuesday May 28, 2013 @01:45PM
(#5781393)
It's not a constraint programming solver, but rather a linear programming solver. The algorithm the comment above used is "branch and bound" on top of the Simplex method to handle the integer constraints.
Tutorial here: http://analyticsmadeskeezy.com/2012/08/29/optimal-blending-o...
Wikipedia here:
http://en.wikipedia.org/wiki/Linear_programming
http://en.wikipedia.org/wiki/Simplex_algorithm
http://en.wikipedia.org/wiki/Branch_and_bound