5.111. domain_constraint

Origin

[Refalo00]

Constraint

domain_constraint​(VAR,​VALUES)​

Argument(s)

VAR	dvar
VALUES	collection​(var01−dvar,​value−int)​

Restriction(s)

required​(VALUES,​​[var01,​value]​)​

VALUES.var01≥0

VALUES.var01≤1

distinct​(VALUES,​value)​

Purpose

Make the link between a domain variable VAR and those 0-1 variables that are associated with each potential value of VAR: The 0-1 variable associated with the value that is taken by variable VAR is equal to 1, while the remaining 0-1 variables are all equal to 0.

Example

( 5,​〈 var01−0 value−9,​ var01−1 value−5,​ var01−0 value−2,​ var01−0 value−7 〉 )

The domain_constraint holds since VAR=5 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.

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 domain_constraint​(VAR,​

                            〈var01−B₁ value−v₁,​

                             var01−B₂ value−v₂,​

                             ........................

                             var01−B_|VALUES| value−v_|VALUES|〉)​

constraint can be expressed in term of the following reified constraint ​(VAR=v₁∧B₁=1)​∨​(VAR=v₂∧B₂=1)​∨...∨​(VAR=v_|VALUES|∧B_|VALUES|=1)​.

Systems

channel in Gecode, in in SICStus, in_set in SICStus.

See also

link_set_to_booleans.

Key words

characteristic of a constraint: automaton, automaton without counters, 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(s)

col​(VALUE−collection​(var01−int,​value−dvar)​,​​[item​(var01−1,​value−VAR)​]​)​

---

Arc input(s)

VALUE VALUES

Arc generator

PRODUCT↦collection​(value,​values)​

Arc arity

2

Arc constraint(s)

value.value=values.value⇔values.var01=1

Graph property(ies)

NARC=|VALUES|

---

Graph model

The domain_constraint constraint is modelled with the following bipartite graph:

• The first class of vertices corresponds to one single vertex containing the domain variable.

• The second class of vertices contains one vertex for each item of the collection VALUES.

PRODUCT is used in order to generate the arcs of the graph. In our context it takes a collection with one single item 〈var01−1 value−VAR〉 and the collection VALUES.

The arc constraint between the variable VAR and one potential value v expresses the following:

• If the 0-1 variable associated with v is equal to 1, VAR is equal to v.

• Otherwise, if the 0-1 variable associated with v is equal to 0, VAR is not equal to v.

Since all arc constraints should hold the final graph contains exactly |VALUES| arcs.

Parts (A) and (B) of Figure 5.111.1 respectively show the initial and final graph associated with the Example slot. Since we use the NARC graph property, the arcs of the final graph are stressed in bold.

Figure 5.111.1. Initial and final graph of the domain_constraint constraint

(a)	(b)

Signature

Since the number of arcs of the initial graph is equal to VALUES the maximum number of arcs of the final graph is also equal to VALUES. Therefore we can rewrite the graph property NARC=|VALUES| to NARC≥|VALUES|. This leads to simplify NARC to NARC.

Automaton

Figure 5.111.2 depicts the automaton associated with the domain_constraint constraint. Let VAR01_i and VALUE_i respectively be the var01 and the value attributes of the i^th item of the VALUES collection. To each triple ​(VAR,​VAR01_i,​VALUE_i)​ corresponds a 0-1 signature variable S_i as well as the following signature constraint: ​(​(VAR=VALUE_i)​⇔VAR01_i)​⇔S_i.

Figure 5.111.2. Automaton of the domain_constraint constraint

Figure 5.111.3. Hypergraph of the reformulation corresponding to the automaton of the domain_constraint constraint