Decomposable operations

[363734]

From the discussion of monday 5 June 2023 at noon:

Minimum, Maximum, Element and Count currently inherits from GlobalConstraint. But they are not really constraints, following the classical definition "constraints define a relation between some variables for which a given assignment satisfies or does not satisfy the constraint". They are in fact more close to operations, evaluated as a value. They are real constraints when used with a comparison. This creates, from an inheritance point of view, multiple problems (decompose function not defined without a comparison,...).

Two possibilities to clean the inheritance: 1) Transforming them into special comparison constraints (Element compare, max compare,...) for which the constructor could accept a default '==' comparison without a defined variable to be compared to. This variable would be created only if needed (if there is a decomposition needed) 2) Creating a Decomposable_Operator abstract class inheriting from Expression directly or maybe Operator ( and being inherited by Min, Max, Element, Count). A comparison constraint comparing a decomposable operator and some other expression could be defined if needed when a decomposition is needed for the decomposable_operators

solution 1 would probably lead to redundant code since the comparison part would be the same for all. Solution 2 would remove the redundancy.

[Wout4]

I like the idea of extracting a different class for these numerical globals (or whatever we want to call them). Will clean up the inheritance a lot indeed. Not a big fan of turning them into 'real' global constraints by adding the result-variable to them however. So i vote #2 ;)

[363734]

I see issue #258 raise the problem that abs should also be decomposable -> we could add it as a decomposable op as min/max/element/count

[tias]

We call them 'numeric global constraints', by lack of better name. I only realized later that constraints like 'Element' need special handling in a language like ours, because they are indeed more like operators/functions returning a numeric value.

1. is no go. Transformations rewrite them to be used in a comparison, and then call decompose_comparison().

What is the benefit of creating two separate abstract classes (e.g. GlobalConstraint and smth like NumericGlobalConstraint or any other better name)? One will have 'decompose' as function, the other 'decompose_comparison'; so mostly conceptual?

Note that any creation of new classes might require creating new 'elif' statements in many places; which I'm not fond of.

[JoD]

They are real constraints when used with a comparison.

No. This is some old-school CP thinking where you had to write constraints as part of a Prolog rule. The philosophy of CPMpy is that one can compose constraints in whatever way, shape or form one desires. x+y is as much (or as little) a constraint as x>y.

This composability is crucial. E.g., is alldiff(x,y, z) a constraint? Let's say yes. Then, is ! alldiff(x,y,z) a constraint? If not, then what is it? Let's say yes, it's Boolean after all. Then, is count(! alldiff(x,y,z), p) a constraint? Most would say no. But then, what is it? And what would count(! alldiff(x,y,z), p) >= 1 be? According to the old-school interpretation, it would now be a constraint again. But why? I'm just repeating the same process -- composing "constraints"...

I don't care what we call them (constraints, terms, expressions, syntax trees, inductively defined strings...), as long as there is no distinction between them. To me, we have primitively typed terms (built as a term tree). I'd be happy to say that we get an actual constraint when we assert some term to have a fixed value. E.g., x | y is a term with type bool, and it becomes a constraint when we assert it to be true (or false, whatever value in the type of the term you want). E.g., x + y is a term with type int, and it becomes a constraint when we assert it to be 0. E.g., max(x,y) is a term with type int, max(x,y)>=3 is a term with type bool, and the latter becomes a constraint when we say that it must be true or false.

Note that thinking of numerical terms as "not-constraints" leads to problems such as "decomposition of circuit behaves weird" (while it behaves the same as decompositions for most numerical terms) or "lets make element undefined until it is part of a comparison" (while this yields inconsistencies as a subterm (!) to negations, xors or counts).

So the central argument is that all terms can be a subterm of some other term in CPMpy. As long as we have that (and we should!) we should make no distinction between constraints, and numerical "not-constraints", simply because we can mix-and-match ad infinitum.

[JoD]

Ok, the above is philosophy. From a practical point of view, I'd be happy to have some code that decomposes the comparison of a numerical term, and re-use that code to decompose the occurrence of a numerical term where it is not part of a comparison.

We can definitely use an inheritable interface (with the appropriate methods) for the terms that use this way of decomposing themselves (e.g., min/max, but also circuit!).

[363734]

For me, x+y is not a constraint, as it does impact x if y is changed and y if x is changed. There is no concept of satisfiability with x+y. x > y, on the other end, is a constraint, as, for it to be satisfied, there is an impact created by the change of one var to the other. CPMpy allows using "classical" constraints as expressions by converting them automatically to a value (0 or 1). It increases the modelization power for something that needed to be done explicitly in other solvers (through what is called reification).

But in the end, CPMpy still requires a constraint to be inputted in the model. You couldn't use x+y as one of the constraints in the model (and should break).

One could say that the classical constraints defined in the literature correspond to boolean expression that we want to be evaluated to true. But for me, not all the expressions are constraints. Just Element(arr, var) is not a constraint, it is simply an expression. Same for max, min, count.

For your example @JoD, alldiff(x,y, z), ! alldiff(x,y,z), count(! alldiff(x,y,z), p) >= 1 are boolean expressions that can be used as constraints by imposing their value to be true, but count(! alldiff(x,y,z), p) is only an integer expression

[tias]

We seem to agree that a constraint is Boolean expression that is asserted to be true. And that CPMpy has Boolean and numeric(integer) expressions.

It also also likely that we will split the class currently called GlobalConstraint into GlobalConstraint and NumericGlobalConstraint as part of the tree-based decomposition pull request, though the names are not decided yet.

And I guess it is exactly those names that Jo is reacting too... The GlobalConstraint class in CPMpy is used to represent not just "Boolean expressions asserted to be true" but just arbitrarily named Boolean expressions (and numeric ones currently). They often correspond to global constraints that solvers support, but in CPMpy they can also be reified, so our name of 'GlobalConstraint' is not accurate in this case.

So although the original remark is now mostly-resolved (yes, we will split them reasonably soon), the new question is: what should we call these two classes, such that CP researchers realize what it sometimes represents, but such that we don't confuse new users about what is and is not called a constraint...

[Dimosts]

This discussion is dangerous to open, especially not in person, as it can take ages to specify what we call a constraint and what not. I agree with the contept that constraints are boolean expressions that through propagation restrict the domains of variables. So, all boolean expressions can be used as a constraint, but nothing is a constraint by default, unless asserted to be true in a model (which triggers also the propagation). But this would not just affect our definition of global constraints in cpmpy, but also in the whole CP community.

I agree on splitting the numeric expressions from the global constraints to a different class (e.g. GlobalFunctions), but the initial GlobalConstraints class should be named as it, as it represents very specific notions of the CP community which would be weird to not include. For anyone in CP, it woulc be very weird to have a CP modelling library that does not mention anything about Global Constraints, just something about boolean expressions. The fact that they can be reified could be explained in the documentation, i.e. that they can also be used as expressions and not only as constraints.

I will open a new PR to split the 2 cases, and we can continue the discussion there :)

[JoD]

Ok, proposal:

• expressions are just that: any expression we can construct. They can be integer or Boolean. They consist of operators, constraints and functions.
• • operators are what we already have
• • constraints are Boolean expressions that are not operators
• • functions are Integer expressions that are not operators
• global constraints are constraints that are asserted to true at top level

Would that make sense?

[Dimosts]

In general yes, I agree

But, based on this, our GlobalConstraints class should change name, as they are boolean expressions that are not always asserted to be true, they can be used as subexpressions in any other expression too.

However, I have strong feelings on keeping the name GlobalConstraints on them, because of the importance of global constraints in CP. Check PR #351 where I did seperate the boolean GlobalConstraints with the numeric ones, and changed the name of the later to GlobalFunctions.

[363734]

I agree with Dimos. If we forget about the history of CP, then we should call the two class boolean (global) expressions and numerical (global) expressions.

But this can be counterintuitive/weird from the perspective of the people used to CP who may not be cooperative/found it weird not to have a global constraint category. It would be better to keep the name GlobalConstraint, and explain in the spec, that in CPMPY, you have an implicit reification mechanism, which allows the constraints to be used as boolean expressions directly. ex: AllDiff(x,y,z) AND AllDiff(a,b,c) could be translated in term of reification as B1 == AllDiff(x,y,z), B2 == AllDiff(a,b,c) and B1 AND B2 (but we do that more efficiently if possible)

[Wout4]

for now we decided to keep the name global constraints (even though they can be used as expressions in reifications) and add a separate class named global functions for things like min max abs and element.