This is an old revision of the document!
Constraint Programming: Basic Modelling Techniques
Symmetry Breaking
The problem is said to contain symmetry if there exist classes of equivalent solutions — solutions, which are called symmetrical because there exist a simple mechanical procedure to obtain one from another. Graph Coloring Problem has a very obvious symmetry — in every solution we can freely swap colors, e.g. every red node repaint as blue, and every blue node repaint as red. Solutions of this kind aren't bad, just redundant, leading to much bigger search space. Symmetry breaking prunes the search space by removing symmetries from the problem.
Graph Coloring
-
Assignment:
-
Look at and comprehend csp_coloring.mzn
model.
Try to solve the csp_coloring_data.dzn
instance.
You can use model created during previous classes
There is a chance, that problem would to difficult to be solved in a reasonable time.
File csp_coloring_data2.dzn
includes info about the largest clique in the graph
Improve model to make use of the info about the largest clique
Try to solve the problem again.
Multi-Knapsack Problem
Redundant Constraints
There is a good chance the problem can be defined in more than a one way. Also you may find a set of constraints that is sufficient to define the problem. That's cool, however there can exist so called “redundant constraints”; redundant because they do not have impact on the number or quality of the solutions. The only reason to include them into the model is that they may contain additional info about the structure of the problem, therefore giving solver an opportunity to prune the search space (most of the solver prune the search space by propagating constraints, redundant constraint may boost this process).
Magic Sequence
-
Assignment:
-
Add redundant constraints, hints:
Compare solving time with and without the redundant constraints.
Smile with satisfaction
Channeling
If you have more than one model of the same problem, you can combine them into one model. Why would one do that? Mostly because some constraints are easier to express with different variables. Other reason could be that the second model often makes a great example of the redundant constraints.
-
Assignment:
Download, extract and comprehend
the model (or use your own)
Add the other problem definition to the problem
Channel constraints from the both models:
Compare running time of the normal and channeled model
Give yourself a high five, however new solvers are good enough to solve n-queens without the channeling. This technique is still valid for the more complicated problems
Reified Constraints
Reification in Constraint Programming means treating the constraint as a first-order citizen, i.e. you can use the constraint as a boolean value in your model. If you've used the bool2int
function in the Magic Sequence problem, you could do that only because the constraint =
has been reified. Reification allows as to create models with “soft constraints” or “conditional constraints”, i.e. one constraint has to be satisfed only if the second one is satisfied too, otherwise they both can ignored. To do that, one has only to reify the constraints and connect them with the implication: constraint1 → constraint2
. Let's practice this quite useful technique :)
Stable Marriage Problem
Problem: There are two classes of objects (men and women, for example) that have to be matched according to their preferences. We say that a matching (marriage) is unstable if both spouses would prefer to be with somebody else. You can read more about this problem on
wikipedia.
Assignment:
-
Add missing variables, constraints
-