3.7.61. Contractible
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(prefix-contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when
and
),
(suffix-contractible wrt ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when and ),
(contractible wrt when and
),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when ),
(suffix-contractible wrt ),
(contractible wrt when ),
(contractible wrt when ),
(suffix-contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when and ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(suffix-contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt ),
(suffix-contractible wrt ),
(suffix-contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(suffix-contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when ),
(contractible wrt when and ),
(contractible wrt when ),
(contractible wrt when and ),
(contractible wrt when ),
(contractible wrt ),
(contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt when ),
(contractible wrt ),
(contractible wrt when and ),
(contractible wrt when ),
(contractible wrt when and ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt when and and ),
(contractible wrt when and ),
(contractible wrt when ),
(contractible wrt when and ),
(contractible wrt when ,
(contractible wrt when ),
(suffix-contractible wrt ),
(suffix-contractible wrt when ),
(suffix-contractible wrt ),
(contractible wrt when ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when and ),
(contractible wrt when ),
(contractible wrt ),
(suffix-contractible wrt ),
(prefix-contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt when ),
(contractible wrt when and ),
(prefix-contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt when and ),
(prefix-contractible wrt ),
(suffix-contractible wrt ),
(prefix-contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt when and
),
(contractible wrt when ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when ,
and ),
(suffix-contractible wrt ),
(contractible wrt when ),
(prefix-contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt ),
(contractible wrt when ),
(prefix-contractible wrt ),
(suffix-contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when ),
(contractible wrt when ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when and
),
(contractible wrt when and
),
(contractible wrt when and
),
(contractible wrt when and
),
() when ,
(contractible wrt when and
),
(contractible wrt when and
),
() when ,
(prefix-contractible wrt ),
(suffix-contractible wrt ),
() when ,
(contractible wrt ),
(),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt ),
(contractible wrt when ),
(contractible wrt ).
A contractible constraint is
a constraint for which, given any satisfied ground instance, one can remove any item from one of its collection arguments,
without affecting that the resulting constraint still holds, assuming all its restrictions hold.
A typical example of a contractible constraint is the constraint:
given any ground satisfied instance, e.g., ,
we can remove any value from its unique argument without affecting that the resulting constraint still holds.
We generalise slightly the original definition of contractibility introduced by [Maher09c]
in the following ways:
The sequence of variables is replaced by a collection. Consequently, variables are replaced by items.
For instance, in the context of the
constraint, we can remove any task from from any satisfied instance without affecting that
the resulting constraint still holds (e.g., if the resource limit is not exceeded at any point in time,
this still is the case if we remove any task, i.e., since task heights are restricted to be non negative).
Since the constraint may have more than one argument, one has to explicitly specify the argument from which
one may remove items.
Items cannot only be removed from the end of a collection like in [Maher09c],
but also from the beginning or from any part.
Allowing to remove items from the beginning is called prefix-contractibility,
while permitting to remove items from the end is called suffix-contractibility.
Removing items from any part is just called contractibility.
As an example, consider the
constraint which forces all sequences of consecutive variables of the collection
to be assigned at least and
at most values from . The constraint
is not contractible w.r.t. the collection , since removing an item in the middle of
creates a new sequence for which the restriction with respect to
and may not hold. However, if we restrict ourselves to removing just a prefix or suffix
from , then the corresponding
constraint still holds, since no new sequence is created.
A constraint may be contractible only if certain restrictions apply to some of its arguments.
This is done by explicitly providing a list of restrictions, each restriction corresponding to
one of the restrictions described in Section 2.2.3.
We call this conditional contractibility.
Given a source and a target constraint (i.e., the target constraint corresponds to the source constraint from which
we remove some items in some arguments) all arguments of the target constraint should be identical to the arguments
of the source constraint, except:
Argument corresponding to a collection from which we remove items.
Argument occurring in the list of conditional restrictions
with of restriction of the form ,
where is an argument corresponding to a collection from which we remove items and a function.
In addition, all restrictions from the list of restrictions should apply both to the source and target constraints.
We now provide two examples of conditional contractibility with respect to the
constraint, which forces to be the number of variables of the collection
that are assigned a value in .
In general is not contractible since removing an item from
may change the value of . However, given a ground satisfied instance for which
is set to 0, we can remove any item from without affecting that the constraint still
holds. In this context, the two arguments and are left unchanged within
the source and the target constraint.
As an illustration, consider the source constraint
and the target constraint
.
Since is set to 0 both in the source and the target constraint and since
is set to the same list of values both in the source and the target constraint, we have that
implies
.
Similarly, when is equal to , all variables are assigned a value in
. In this context, we can remove any variable from to get a new
constraint that still holds, provided that the restriction still holds.
In this example only the argument is left unchanged between
the source and the target constraint. changes since it occurs in a restriction of the form
in the list of conditional restrictions.
As an illustration, consider the source constraint
and the target constraint
.
Since is set to the number of items of the collection
both in the source and the target constraint, and since is set to the same list of values
both in the source and the target constraint, we have that
implies
.
Finally, a last extension corresponds to the fact that the sequence of variables from which we remove elements
may be replaced by several collections. In this context, items are removed simultaneously from all collections
from exactly the same set of positions. A set of collections is either defined by a list of collections, or by a collection
and one of its attributes, which is itself a collection.
As a first example, consider the
constraint, which given two vectors each defined by a collection of variables of the same length, forces
that is lexicographically greater than or equal to .
We have that is suffix-contractible
with respect to and . This means that we can remove
the last items from collections and
.
Note that the items should be removed from both collections simultaneously.
As an illustration, consider the source constraint
and the target constraint
.
Since is suffix-contractible with respect
to the two collections and , we have that
implies
.
As a second example, consider the
constraint, which given a collection of vectors each of them defined by a collection of variables of the same length,
forces the vector to be lexicographically less than or equal to the vector
.
We have that is suffix-contractible
with respect to . This means that we can remove the last components
of each vectors of the collection. As in the previous example the items should be removed
from all collections simultaneously.
As an illustration, consider the source constraint
and the target constraint
.
Since is suffix-contractible with respect
to , we have that
implies
.
The keyword extensible introduces a dual notion, where items can be added
to a collection that is passed as an argument of a satisfied global constraint without affecting the fact
that the resulting constraint is satisfied. Contractibility is a more common property than extensibility.