5.73. consecutive_groups_of_ones

DESCRIPTIONLINKSAUTOMATON
Origin

Derived from πšπš›πš˜πšžπš™

Constraint

πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ(π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš—πš‹-πš’πš—πš)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚,πš—πš‹)
|π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚|β‰₯1
π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚.πš—πš‹β‰₯1
π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚.πš—πš‹β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|β‰₯πšœπšžπš–(π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚.πš—πš‹)+|π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚|-1
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰₯0
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰€1
Purpose

In order to define the meaning of the πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ constraint, we first introduce the notions of stretch and span. Let n be the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and let m be the number of items of the collection π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚. Let X i ,...,X j (1≀i≀j≀n) be consecutive variables of the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ such that the following conditions apply:

  • All variables X i ,...,X j are assigned value 1,

  • i=1 or X i-1 β‰ 1,

  • j=n or X j+1 β‰ 1.

We call such a set of variables a stretch. The span of the stretch is equal to j-i+1. We now define the condition enforced by the πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ constraint.

All variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection should be assigned value 0 or 1. In addition there is |π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚| successive stretches of respective span π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚[1].πš—πš‹, π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚[2].πš—πš‹,..., π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚[m].πš—πš‹.

Example
2,1,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›-1,πšŸπšŠπš›-0

The πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ constraint holds since the sequence 1 1 0 0 0 1 0 contains a first stretch (i.e.,Β a maximum sequence of 1) of span 2 and a second stretch of span 1.

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

Items of π™Άπšπ™Ύπš„π™Ώ_πš‚π™Έπš‰π™΄πš‚ and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are simultaneously reversable.

Usage

The πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ constraint can be used in order to model the logigraphe problem.

See also

root concept: πšπš›πš˜πšžπš™.

Keywords

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

constraint network structure: Berge-acyclic constraint network.

filtering: arc-consistency.

modelling exercises: logigraphe.

puzzles: logigraphe.

Automaton

FigureΒ 5.73.1 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.73.1. Automaton of the πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ constraint of the Example slot
ctrs/consecutive_groups_of_ones1
Figure 5.73.2. Hypergraph of the reformulation corresponding to the automaton of the πšŒπš˜πš—πšœπšŽπšŒπšžπšπš’πšŸπšŽ_πšπš›πš˜πšžπš™πšœ_𝚘𝚏_πš˜πš—πšŽπšœ constraint of the Example slot
ctrs/consecutive_groups_of_ones2