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

Posted 10 years ago
6756 Views
|
6 Replies
|
4 Total Likes
|
 Reduce and FindInstance can only handle very small constraint programming problems.
6 Replies
Sort By:
Posted 9 years ago
 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.
Posted 10 years ago
 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.
Posted 10 years ago
 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
Posted 10 years ago
Posted 10 years ago
 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.
Posted 10 years ago
 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
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.