Is there a way to customize int_search in minizinc?

Question

I am dealing with graph coloring problem and want to know if I can specify the search strategy. I found the search annotations, such as int_search(q, first_fail, indomain_min), but for example, I want the algorithm to choose the next nodes with the highest node degree in the assumption that it will lead to quicker failures since nodes with a high degree remove the color from the domain of many variables (its neighbors). So can I do that?

Answer 1

(Here I assume that by degree you mean the number of variables that is connected to a specific variable.)

Unfortunately, MiniZinc don't supports user-defined search strategies. See the complete listing of supported search annotations: https://www.minizinc.org/doc-2.5.5/en/fzn-spec.html#annotations .

(MiniSearch, https://www.minizinc.org/minisearch/documentation.html, is an old project that was meant to give this functionality, but it's not integrated in the current version of MiniZinc. I hope that MiniZinc v3 will have this functionality.)

Also, MiniZinc don't have any reflection function for getting the degrees of a variable, otherwise one could have used that for the search.

The closest existing search strategies are probably:

• dom_w_deg: Choose the variable with the smallest value of domain size divided by weighted degree, where the weighted degree is the number of times the variables been in a constraint which failed

• occurrence: Choose the variable with the largest number of attached constraints`

Note that it's not certain that all FlatZinc solvers support these search strategies.

(occurence has - by the way - been a favorite to try if first_fail don't work as well as expected for traditional CP solvers.)

Another thing: There are some FlatZinc solvers - especially Chuffed,Google OR-tools CP-SAT, and perhaps PicatSAT - that use SAT / Lazy clause technology, that is often much faster with the free search flag (-f), i.e. ignoring the search annotations, and they are - if possible - often good to at least try. You can see the performance of the FlatZinc solver at the last year's MiniZinc Challenge: https://www.minizinc.org/challenge2020/results2020.html

Nowadays, I tend to use test larger models with a couple of FlatZinc solvers, especially the one mentioned above.