Order of constraints affects solution time

[Paul Chisholm]

Hi,

I have a model where by swapping the order of two constraints there is a five fold difference in the time it takes to solve. What causes this difference in the order of constraints, and are there any general guidelines on how best to order?

Thanks,

Paul

[Jip Dekker]

Hi Paul,

Although this would, of course, be a problem that we would like to avoid with MiniZinc, there are certainly situations where this currently can happen and some situations where this might be unavoidable. First, in the MiniZinc compiler, the compiler while flattening will occasionally use the domains of variables as part of the decomposition, e.g. when constructing a big-M constraint or choosing a decomposition based on whether a value is fixed. If you have some constraints that might would restrict the domains that are later inspected as part of the decomposition process, then placing these constraints first can have a big impact. It should be noted that it can be hard for the compiler to recover this information, as it currently wouldn't "re-flatten" when we learn new information.

The second source of different behaviour comes from the solver. Some of them behave differently when given the constraints in different order. This generally has to do with heuristics in the solver. MIP solvers are notorious for this, where (as I understand it) the results of preprocessing change depending on the order of constraints, leading to very different results.

Cheers,

Jip

[Paul Chisholm]

Hi Jip,

Thanks for the prompt response. I’ll review my model in light of your comments.

One more question. Through a Google search I happened across a paper “Enumerated Types and Type Extensions for MiniZinc” (Stuckey/Tack) that describes a nice feature:

% Each robot is in a team with the skills to run it

constraint forall(z in ZONE, R(r) in x[z,..])

    (exists(P(p) in x[z,..])(r in skills[p]));

I tried to make use of this feature in a model. The following is a stripped down version that captures the essence:

enum base = {a,b,c};

enum ext = X(base) ++ Y(base);

constraint exists(X(i) in ext, Y(j) in ext)(i=j);

and results in the error “Illegal expression in generator call”. Rewriting to

constraint exists(i,j in base, x in ext where x = X(i), y in ext where y = Y(j))(i=j);

all is well. Is the form described in the paper supported in the current MiniZinc implementation?

Thanks,
Paul

--
You received this message because you are subscribed to the Google Groups "MiniZinc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/minizinc/2c67248a-739f-475c-b9cf-49ef159f7ce8n%40googlegroups.com.

[Jip Dekker]

That syntax with the constructors as part of the identifier never made it into the MiniZinc releases. I would indeed write the second variant, although it can be simplified by using the assignment syntax within generators:

constraint exists(i, j in base, x = X(i), y = Y(j))( i = j );

[Paul Chisholm]

Great, thanks very much for your help Jip.

Paul

To view this discussion visit https://groups.google.com/d/msgid/minizinc/b74a1f8c-d354-4863-89c6-626e94dd6a37n%40googlegroups.com.