Has Anyone Figured Out How to do Constraint Programming in Mathematica?

Questions
,
1

Reduce and FindInstance can only handle very small constraint programming problems.

2

http://reference.wolfram.com/mathematica/tutorial/ConstrainedOptimizationOverview.html

3

Constraint Programming and Constrained Optimization are not really the same thing. An example of constraint programming is the 8 queens problem, how to put 8 queens on a chess board so that they can’t attack each other. There’s no objective function.

4

Thanks. Yes, I see that they are maybe harder problems to generalize.

I just saw this on the website, wrt 8 queens problem: Queens on a Chessboard

5

Mathematica doesn’t really do logic programming (like prolog). It’s not hard to implement something though:

The Mathematica Programmer: Logic Programming I: The Interpreter

6

Looking in my collection of Mathematica books, I see I have “The Mathematica Programmer II” by Roman Maeder, which has a a chapter on Logic Programming, which contains the infocenter article.

7

I’ve done some experimenting on a graph coloring problem with 20 nodes and 23 edges, coloring the nodes with 3 different colors.
Using FindInstance with Integer variables I can solve the problem in about 3 seconds. Using FindInstance with 3 Boolean variables on each node, I can solve the problem in about 1.5 seconds. Converting the problem to a mixed integer linear programming formulation with 3 binary variables on each node, I can solve the problem in 11 mSec using NMinimize. For the FindInstance approach with 3 Boolean variables on each node, I used the BooleanCountingFunction to generate the constraints that only one variable on each node is True and that at most one variable is True for the corresponding variables on nodes connected by edges.