5.143. global_contiguity

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[Maher02]

Constraint

πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonym

πšŒπš˜πš—πšπš’πšπšžπš’πšπš’.

Argument
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰₯0
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰€1
Purpose

Enforce all variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection to be assigned value 0 or 1. In addition, all variables assigned to value 1 appear contiguously.

Example
(0,1,1,0)

The πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint holds since the sequence 0 1 1 0 contains no more than one group of contiguous 1.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

Usage

The articleΒ [Maher02] introducing this constraint refers to hardware configuration problems.

Algorithm

A filtering algorithm for this constraint is described inΒ [Maher02].

See also

common keyword: πšπš›πš˜πšžπš™, πš’πš—πšπš•πšŽπš‘πš’πš˜πš—Β (sequence).

implies: πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšŸπšŠπš•πšžπšŽπšœ, πš—πš˜_πšŸπšŠπš•πš•πšŽπš’.

related: πš›πš˜πš˜πšπšœ.

Keywords

characteristic of a constraint: convex, automaton, automaton without counters, reified automaton constraint.

combinatorial object: sequence.

constraint network structure: Berge-acyclic constraint network.

filtering: arc-consistency.

final graph structure: connected component.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)
πΏπ‘‚π‘‚π‘ƒβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=1
Graph property(ies)
𝐍𝐂𝐂≀1

Graph model

Each connected component of the final graph corresponds to one set of contiguous variables that all take value 1.

PartsΒ (A) andΒ (B) of FigureΒ 5.143.1 respectively show the initial and final graph associated with the Example slot. The πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint holds since the final graph does not contain more than one connected component. This connected component corresponds to 2 contiguous variables that are both assigned to 1.

Figure 5.143.1. Initial and final graph of the πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint
ctrs/global_contiguityActrs/global_contiguityB
(a) (b)
Automaton

FigureΒ 5.143.2 depicts the automaton associated with the πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint. To each variable πš…π™°πš i of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable that is equal to πš…π™°πš i . There is no signature constraint.

Figure 5.143.2. Automaton of the πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint
ctrs/global_contiguity1
Figure 5.143.3. Hypergraph of the reformulation corresponding to the automaton of the πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint
ctrs/global_contiguity2