5.136. domain_constraint
DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
- Constraint
- Synonym
.
- Arguments
- Restrictions
- Purpose
Make the link between a domain variable and those 0-1 variables that are associated with each potential value of : The 0-1 variable associated with the value that is taken by variable is equal to 1, while the remaining 0-1 variables are all equal to 0.
- Example
-
The holds since is set to the value corresponding to the 0-1 variable set to 1, while the other 0-1 variables are all set to 0.
- Typical
- Symmetry
Items of are permutable.
- Usage
This constraint is used in order to make the link between a formulation using finite domain constraints and a formulation exploiting 0-1 variables.
- Reformulation
The
Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β
Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β
Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β
Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β
constraint can be expressed in term of the following reified constraint .
- Systems
domainChanneling in Choco, channel in Gecode, in in SICStus, in_set in SICStus.
- See also
common keyword: Β (channelling constraint).
related: .
- Keywords
characteristic of a constraint: automaton, automaton without counters, reified automaton constraint, derived collection.
constraint network structure: centered cyclic(1) constraint network(1).
constraint type: decomposition.
filtering: linear programming, arc-consistency.
modelling: channelling constraint, domain channel, Boolean channel.
- Derived Collection
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
The constraint is modelled with the following bipartite graph:
The first class of vertices corresponds to a single vertex containing the domain variable.
The second class of vertices contains one vertex for each item of the collection .
is used in order to generate the arcs of the graph. In our context it takes a collection with a single item and the collection .
The arc constraint between the variable and one potential value expresses the following:
If the 0-1 variable associated with is equal to 1, is equal to .
Otherwise, if the 0-1 variable associated with is equal to 0, is not equal to .
Since all arc constraints should hold the final graph contains exactly arcs.
PartsΒ (A) andΒ (B) of FigureΒ 5.136.1 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, the arcs of the final graph are stressed in bold.
Figure 5.136.1. Initial and final graph of the constraint
(a) (b) - Signature
Since the number of arcs of the initial graph is equal to the maximum number of arcs of the final graph is also equal to . Therefore we can rewrite the graph property to . This leads to simplify to .
- Automaton
FigureΒ 5.136.2 depicts the automaton associated with the constraint. Let and respectively be the and the attributes of the item of the collection. To each triple corresponds a 0-1 signature variable as well as the following signature constraint: .
Figure 5.136.2. Automaton of the constraint
Figure 5.136.3. Hypergraph of the reformulation corresponding to the automaton of the constraint: since all states variables are fixed to the unique state of the automaton, the transitions constraints involve only a single variable and the constraint network is Berge-acyclic