New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Compilation of xorall in reification context seems to be wrong #146

Closed
informarte opened this Issue Feb 25, 2017 · 4 comments

Comments

Projects
None yet
2 participants
@informarte

informarte commented Feb 25, 2017

In the parity-learning problem (part of the MiniZinc benchmarks library), we have the following constraint:

constraint forall(s in SAMPLES)( computed_parities[s] = xorall(v in VARS)( parity_bits[v] /\ sample_inputs[s,v]) );

This constraint translates to s bool_array_xor constraints like this one for s = 1 in the 44_22_5.3 instance,:

constraint array_bool_xor(X_INTRODUCED_200):: defines_var(X_INTRODUCED_22);

where

array [1..44] of var bool: computed_parities:: output_array([1..44]) = [X_INTRODUCED_22, ...];

So I expected to find X_INTRODUCED_22 (or some variable equal to it) in X_INTRODUCED_200 but it is not there.

In fact it seems that all the computed_parities end up as unconstrained search variables.

(I am using MiniZinc 2.0.14.)

@informarte informarte changed the title from Compilation of xorall seems to be wrong to Compilation of xorall in reification context seems to be wrong Feb 25, 2017

@guidotack

This comment has been minimized.

Member

guidotack commented Feb 27, 2017

The annotation is indeed misleading, but as far as I can see the compilation is correct. The negation of X_22 is X_199, which appears in X_200. I'll look into a fix for the spurious defines_var annotation on the xor, it should really say defines_var(X_INTRODUCED_199).

@informarte

This comment has been minimized.

informarte commented Feb 27, 2017

Guido, this is the negation constraint you referred to:

constraint bool_eq_reif(X_INTRODUCED_22,false,X_INTRODUCED_199):: defines_var(X_INTRODUCED_199);

So we would end up with two constraints defining X_INTRODUCED_199 which is clearly not the dataflow intended by the model author. I would rather expect to see:

constraint array_bool_xor(X_INTRODUCED_200):: defines_var(X_INTRODUCED_199);
constraint bool_not(X_INTRODUCED_199, X_INTRODUCED_22):: defines_var(X_INTRODUCED_22);

Btw, I wonder why there is no array_bool_xor/2 constraint.

@guidotack

This comment has been minimized.

Member

guidotack commented Feb 28, 2017

That's the constraint. As I said earlier, the annotations are currently not generated correctly. The negation should define X_22, not X_199.
The reason there's no array_bool_xor/2 is that xor([a,b],c) is equal to xor([a,b,-c]), so it seemed unnecessary. In fact we should move this into the redefinitions so that solvers that do implement reified xor can use it directly without the need for an extra negation.

You can try out the fix I just pushed by replacing the definition of xorall_reif in builtins.mzn with the following:

predicate xorall_reif(array[int] of var bool: b, var bool: c) =
  let { var bool: nc ::is_defined_var; constraint xorall([nc]++b) ::defines_var(nc); } in c = not nc;
@informarte

This comment has been minimized.

informarte commented Mar 4, 2017

Works fine, thank you!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment