A CP Solution for XKCD NP Complete Restaurant Order

Re:A CP Solution for XKCD NP Complete Restaurant Order by mistermcgruff on Tuesday May 28, 2013 @10:30AM (#5780243)

Personally, I'd solve this using an integer programming approach, but CP is really cool.

The IBM CPLEX CP optimizer is best for this kind of stuff IMHO.

[ Parent | on HN ]

Re:A CP Solution for XKCD NP Complete Restaurant Order by hartror on Tuesday May 28, 2013 @06:48PM (#5783370)

We use CPLEX for LPs but I've not read much on the CPLEX CP solver. Maybe because it isn't free so the academics stick with the OSS ones? How does it compare to gecode?

[ Parent | on HN ]

Re:A CP Solution for XKCD NP Complete Restaurant Order by mzl on Wednesday May 29, 2013 @01:09AM (#5784699)

One of the driving forces behind the development of Gecode was that academics used to use the pre-cursor to IBM CP Optimizer, ILOG Solver, in research.

As for comparing Gecode with CP Optimizer, the largest difference IBM CP Optimizer is a closed-source commercial system, with paid support. CP Optimizer also has some (as far as I've seen) amazing automatic search heuristics, automatic symmetry breaking, and more advanced scheduling constraints. Gecode on the other hand is open for modifications, has nice parallel search built in, and can be embedded easily. Given a problem where both systems have the constraints, and the search heuristic is fixed, my guess is that they would be mostly equivalent in speed

[ Parent | on HN ]

Re:A CP Solution for XKCD NP Complete Restaurant Order by hartror on Wednesday May 29, 2013 @03:00AM (#5785036)

I have a cplex license on my work machine so that is another avenue to explore!

[ Parent | on HN ]

Re:A CP Solution for XKCD NP Complete Restaurant Order by mzl on Wednesday May 29, 2013 @03:03AM (#5785049)

Note that CPLEX and CP Optimizer are two completely different products. AFAIK, a license key for one of them can not be used for the other. But I've never actually used either myself, so don't take my word for it.

Also, since you seem to be interested in using Minizinc for modelling, you can use other back-ends than the built in one for solving models.

For some more code examples, see also Håkan Kjellerstrands blog (http://www.hakank.org/constraint_programming_blog/) which, among other things, contains numerous solutions to the xkcd problem suing different systems.

[ Parent | on HN ]

Re:A CP Solution for XKCD NP Complete Restaurant Order by hartror on Wednesday May 29, 2013 @03:26AM (#5785108)

I have tested out using gecode as a minizinc backend as I like the look of gint. I've been skimming hakank.org but it is a little advance for me at the moment.

Is there a way to get a minizinc model into cp optimizer?

[ Parent | on HN ]

Re:A CP Solution for XKCD NP Complete Restaurant Order by mzl on Wednesday May 29, 2013 @04:35AM (#5785263)

I have no idea if it is possible to use Minizinc models with CP Optimizer, but I would guess not. It doesn't feel like a feature that would be of business interest to IBM to develop.

As for Håkans pages, http://www.hakank.org/common_cp_models/#xkcd has a list of 21 implementations of the xkcd problem.

[ Parent | on HN ]