The problem is said to contain symmetry if there are 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.

• Problem: Same as before
• Assignment:
  1. Download and extract |archive.
  2. Look at and comprehend csp_coloring.mzn model.
  3. 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.
  4. File csp_coloring_data2.dzn includes info about the largest clique in the graph
     • minColorsNumber - size of the largest clique
     • maxClique - indexes of the vertices forming the largest clique
  5. Improve model to make use of the info about the largest clique
  6. Try to solve the problem again.

• Definition: Knapsack problem with several identical knapsacks instead of one.
• Assignment:
  1. Find a symmetry in the problem.
  2. Download and extract the archive
  3. Look at and comprehend csp_n_knapsack.mzn.
     • Note : this model is not an example of good constraint model; it's just used to show a common technique to break symmetries
     • Note use of the at_most global constraint.
     • There is a defined predicate named knapsack → it's the first example of user defined predicate
  4. Run model with the associated data file:
     • The problem may be to hard for the solver
  5. Break symmetry using ''lex_less'' global constraint.
  6. Run new model with the same data file

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).

• Definition: Same as before
• Assignment:
  1. Download, extract, comprehend model
  2. Add redundant constraints, hints:
     • what should be equal the sum of the magic sequence?
     • what should be equal the sum of sequence elements multiplied by their indexes (if indexing starts from 0)?
  3. Compare solving time with and without the redundant constraints.
  4. Smile with satisfaction

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.

• Problem: N-Queens again
• Assignment:
  1. Download, extract and comprehend csp_n_hetmans.zip (or use your own model)
  2. Add the other problem definition to the problem
     • Example: if the queens were assigned to the columns, you may now assign them to the rows
  3. Channel constraints from the both models:
     • You may use channeling constraint ''inverse''
  4. Compare running time of the normal and channeled model
  5. 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

So far we haven't talked about the way solver looks for the solution. There are many different techniques to solve to constraint programming problem, however basic techniques often perform a DFS (backtracking) search with two steps at every node:

1. select variable — choose, which variable will receive a value in this step
2. select value — choose, which value from the variable's domain will be chosen

You may control this procedure in MiniZinc using search annotations just after the solve keyword. e.g.

solve :: int_search(array, first_fail, indomain_min, complete) satisfy;

mean that że integer (int) variables from the array should be search exhaustively (complete) according to the simple strategy:

• select variable which has to lowest amount of available values (first_fail)
• select the smallest available value (indomain_min).

In order to define more interesting search strategies one has to use so called MiniSearch language, which still isn't a part of the MiniZincIDE package.

• Definition: same as always.
• Assignments:
  1. Run model using Gecode (Gist, bundled) solver — select it in the configuration tab
     • play with the search :)
  2. Check four different search strategies

     int_search(rows, input_order, indomain_min, complete);
     int_search(rows, input_order, indomain_median, complete);
     int_search(rows, first_fail, indomain_min, complete);
     int_search(rows, first_fail, indomain_median, complete);

  3. Read about the different strategies. Select one according to your taste.
  4. Compare solving time of the problem using different stragies.
  5. Don't worry, be happy.