Search code examples
constraint-programmingminizinc

Can I specify the order in which the possible values are tried for a variable?

I'm performing clustering on Minizinc on huge dataset but my computational time is huge and I'm trying to reduce it. To do so, I would like to specify the order in which the possible values are tried for a variable.

For example, a variable v as a domain 1..5, but I know that 4 is more likely than 3, 3 is more likely than 2, ect. In this case, is there a way for me to say that I want 4 to be tried first, then 3, then 2, etc.?

Solution

  • Although there is a way of setting a preselected order in which we search over variables (the input_order variable choice heuristic), there is currently no value choice heuristic that does the same for the order in which values are tried.

    There are, however, many other value choice heuristics in MiniZinc: https://www.minizinc.org/doc-2.5.5/en/lib-stdlib.html#value-choice-annotations. If you are looking for a portable value choice heuristic, then you will probably find one that approximates the distribution in the problem that you are looking for.

    As a side note, it might be good to consider what will actually perform best in a CP solver. Although choose the most likely candidate can lead to good results, sometimes the best search strategy is actually to fail quickly. If you know that at least some variables have to take an unlikely value and it is easier to prove failure than find a solution, then it is often better to first try the choices that would lead to failures. These failures will quickly further the search, where to find out that a good guess is not a solution might take a lot of search. In the end, the best thing is to try many search heuristics. It might often surprise you what works best.

    Some other things to consider:

    • If you don't need a portable solution, then you can see what value choice heuristics are available for individual solvers. Some solver will add solver specific choices in an include file with the name of the solver (e.g., chuffed.mzn and gecode.mzn). These include some search heuristics.
    • You can try using "learning solvers". LCG solvers like Chuffed and OR-Tools will generate new constraints (Boolean clauses) from previous failures in the search process. This mechanism can significantly reduce the search space and emulate smarter search heuristics.
    • If you can imagine a heuristic that gives a partial or initial solution for your problem you can try MiniZinc's warm start functionality (https://www.minizinc.org/doc-2.5.5/en/mzn_search.html#warm-starts). This is not yet supported by all solvers.