5.168. 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.

All solutions

FigureΒ 5.168.1 gives all solutions to the following non ground instance of the πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint: V 1 ∈[0,1], V 2 ∈[0,1], V 3 =1, V 4 ∈[0,1], πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’(〈V 1 ,V 2 ,V 3 ,V 4 βŒͺ).

Figure 5.168.1. All solutions corresponding to the non ground example of the πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint of the All solutions slot
ctrs/global_contiguity-1-tikz
Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
πšŠπšπš•πšŽπšŠπšœπš(2,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,1)
Symmetry

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

Arg. properties

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

Usage

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

Algorithm

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

Counting

Length (n)23456789101112131415161718192021222324
Solutions4711162229374656677992106121137154172191211232254277301

Number of solutions for πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’: domains 0..1

ctrs/global_contiguity-2-tikz

ctrs/global_contiguity-3-tikz

See also

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

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

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

Keywords

characteristic of a constraint: convex, automaton, automaton without counters, automaton with same input symbol, reified automaton constraint.

combinatorial object: sequence.

constraint network structure: Berge-acyclic constraint network.

filtering: arc-consistency.

final graph structure: connected component.

Cond. implications

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

Β Β Β  withΒ  |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2

Β Β implies πšœπš˜πš–πšŽ_πšŽπššπšžπšŠπš•(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚).

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.168.2 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.168.2. Initial and final graph of the πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint
ctrs/global_contiguityActrs/global_contiguityB
(a) (b)
Automaton

FigureΒ 5.168.3 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.168.3. Automaton of the πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint
ctrs/global_contiguity-4-tikz
Figure 5.168.4. Hypergraph of the reformulation corresponding to the automaton of the πšπš•πš˜πš‹πšŠπš•_πšŒπš˜πš—πšπš’πšπšžπš’πšπš’ constraint
ctrs/global_contiguity-5-tikz