Message Boards Message Boards

6 Replies
4 Total Likes
View groups...
Share this post:

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

Reduce and FindInstance can only handle very small constraint programming problems.
POSTED BY: Frank Kampas
6 Replies
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 BY: Frank Kampas
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 BY: Frank Kampas
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 BY: Sean Clarke
Posted 11 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 BY: Frank Kampas
Posted 11 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
POSTED BY: Priyan Fernando
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract