Sampling search domain

Question

In Minizinc, is it possible to sample the domain ? lets say my domain has many solutions, running --all-solutions will initially return very similar solutions.

1) is there a way to sample the domain ? perhaps BFS ? the purpose is for follow up solutions analysis.

2) Is there any methods to estimate search domain size in CP?

my domain is a Staff Rostering Problem

Regards, H

Answer 1

1. It is not possible to choose BFS in MiniZinc but there is search annotations. With the search annotations you can choose in which order the variables should be branched on. You can also choose which value will be branched on. Unfortunately, MiniZinc does not support random variable search.

   In your case I would branch on a dom_w_deg with a random value but any other variable selection can work, try them.

   solve::seq_search([int_search(some_array, dom_w_deg, indomain_random,complete)]) satisfy;
   

   Do note that not all solvers support the usage of search annotations.

   Other alternatives are to add constraints that remove the similar results.

2. You can always calculate the number of permutations you can have in your solution, the number of variables multiplied with their domain. This will not consider any constraints and the real search space can be much smaller.

Another way of visualizing the search is by using gist or other programs to visualize the search.

_{(source: marco at www.imada.sdu.dk)}

You can expand and retract parts of the search tree and see which variables have been branched on.