search

CPMpy / cpmpy

Constraint Programming and Modeling library in Python, based on numpy, with direct solver access.
Apache License 2.0
234 stars 26 forks source link

Xor decomposition is very inefficient #395

Closed Wout4 closed 1 year ago

Wout4 commented 1 year ago

[IV147,IV148,IV149,IV137,IV138,IV139]= intvar(0,4,6) errey = cp.cpm_array([IV147,IV148, IV149, IV137, IV138]) const = [Xor([(errey[IV137] == 0), (errey[IV138] == 1), (errey[IV139] == 2)])] const = decompose_in_tree(const) const = flatten_constraint(const) print(len(const)) = 601147

This simple constraint flattens into 600000 constraints! The problem is our recursive decomposition of Xor, it introduces a lot of disjunctions. Maybe it will be better with cse already but we can do better in the decomposition of xor as well

Wout4 commented 1 year ago

this is actually related to the problem in flattening (#399 ), removing the rule for applying distributivity of disjunctions and conjunctions there leads to only 185 flat constraints (with more aux vars but still preferable obviously)