5.114. domain_constraint

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[Refalo00]

Constraint

πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš(πš…π™°πš,πš…π™°π™»πš„π™΄πš‚)

Synonym

πšπš˜πš–πšŠπš’πš—.

Arguments
πš…π™°πšπšπšŸπšŠπš›
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›01-πšπšŸπšŠπš›,πšŸπšŠπš•πšžπšŽ-πš’πš—πš)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,[πšŸπšŠπš›01,πšŸπšŠπš•πšžπšŽ])
πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš›01β‰₯0
πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš›01≀1
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•πšžπšŽ)
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
5,πšŸπšŠπš›01-0πšŸπšŠπš•πšžπšŽ-9,πšŸπšŠπš›01-1πšŸπšŠπš•πšžπšŽ-5,πšŸπšŠπš›01-0πšŸπšŠπš•πšžπšŽ-2,πšŸπšŠπš›01-0πšŸπšŠπš•πšžπšŽ-7

The πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš holds since πš…π™°πš=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.

Typical
|πš…π™°π™»πš„π™΄πš‚|>1
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 πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš(πš…π™°πš,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β βŒ©πšŸπšŠπš›01-B 1 πšŸπšŠπš•πšžπšŽ-v 1 ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β πšŸπšŠπš›01-B 2 πšŸπšŠπš•πšžπšŽ-v 2 ,

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β ........................

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β πšŸπšŠπš›01-B |πš…π™°π™»πš„π™΄πš‚| πšŸπšŠπš•πšžπšŽ-v |πš…π™°π™»πš„π™΄πš‚| βŒͺ)

constraint can be expressed in term of the following reified constraint (πš…π™°πš=v 1 ∧B 1 =1)∨(πš…π™°πš=v 2 ∧B 2 =1)∨...∨(πš…π™°πš=v |πš…π™°π™»πš„π™΄πš‚| ∧B |πš…π™°π™»πš„π™΄πš‚| =1).

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
πšŒπš˜πš•πš…π™°π™»πš„π™΄-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›01-πš’πš—πš,πšŸπšŠπš•πšžπšŽ-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšŸπšŠπš›01-1,πšŸπšŠπš•πšžπšŽ-πš…π™°πš)]
Arc input(s)

πš…π™°π™»πš„π™΄ πš…π™°π™»πš„π™΄πš‚

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•πšžπšŽ,πšŸπšŠπš•πšžπšŽπšœ)

Arc arity
Arc constraint(s)
πšŸπšŠπš•πšžπšŽ.πšŸπšŠπš•πšžπšŽ=πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš•πšžπšŽβ‡”πšŸπšŠπš•πšžπšŽπšœ.πšŸπšŠπš›01=1
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°π™»πš„π™΄πš‚|

Graph model

The πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš 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 πš…π™°π™»πš„π™΄πš‚.

π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ is used in order to generate the arcs of the graph. In our context it takes a collection with one single item βŒ©πšŸπšŠπš›01-1 πšŸπšŠπš•πšžπšŽ-πš…π™°πšβŒͺ and the collection πš…π™°π™»πš„π™΄πš‚.

The arc constraint between the variable πš…π™°πš and one potential value v expresses the following:

  • If the 0-1 variable associated with v is equal to 1, πš…π™°πš is equal to v.

  • Otherwise, if the 0-1 variable associated with v is equal to 0, πš…π™°πš is not equal to v.

Since all arc constraints should hold the final graph contains exactly |πš…π™°π™»πš„π™΄πš‚| arcs.

PartsΒ (A) andΒ (B) of FigureΒ 5.114.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.114.1. Initial and final graph of the πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš constraint
ctrs/domain_constraintActrs/domain_constraintB
(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.114.2 depicts the automaton associated with the πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš constraint. Let πš…π™°πš01 i and πš…π™°π™»πš„π™΄ i respectively be the πšŸπšŠπš›01 and the πšŸπšŠπš•πšžπšŽ attributes of the i th item of the πš…π™°π™»πš„π™΄πš‚ collection. To each triple (πš…π™°πš,πš…π™°πš01 i ,πš…π™°π™»πš„π™΄ i ) corresponds a 0-1 signature variable πš‚ i as well as the following signature constraint: ((πš…π™°πš=πš…π™°π™»πš„π™΄ i )β‡”πš…π™°πš01 i )β‡”πš‚ i .

Figure 5.114.2. Automaton of the πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš constraint
ctrs/domain_constraint1
Figure 5.114.3. Hypergraph of the reformulation corresponding to the automaton of the πšπš˜πš–πšŠπš’πš—_πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš constraint
ctrs/domain_constraint2