5.21. among_seq

DESCRIPTIONLINKSGRAPH
Origin

[BeldiceanuContejean94]

Constraint

πšŠπš–πš˜πš—πš_𝚜𝚎𝚚(π™»π™Ύπš†,πš„π™Ώ,πš‚π™΄πš€,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)

Synonym

πšœπšŽπššπšžπšŽπš—πšŒπšŽ.

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

Constrains all sequences of πš‚π™΄πš€ consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ to take at least π™»π™Ύπš† values in πš…π™°π™»πš„π™΄πš‚ and at most πš„π™Ώ values in πš…π™°π™»πš„π™΄πš‚.

Example
1,2,4,πšŸπšŠπš›-9,πšŸπšŠπš›-2,πšŸπšŠπš›-4,πšŸπšŠπš›-5,πšŸπšŠπš›-5,πšŸπšŠπš›-7,πšŸπšŠπš›-2,0,2,4,6,8

The πšŠπš–πš˜πš—πš_𝚜𝚎𝚚 constraint holds since the different sequences of 4 consecutive variables contains respectively 2, 2, 1 and 1 even numbers.

Typical
π™»π™Ύπš†<πš‚π™΄πš€
πš„π™Ώ>0
πš‚π™΄πš€>1
πš‚π™΄πš€<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
|πš…π™°π™»πš„π™΄πš‚|>0
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>|πš…π™°π™»πš„π™΄πš‚|
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

  • Items of πš…π™°π™»πš„π™΄πš‚ are permutable.

  • π™»π™Ύπš† can be decreased to any value β‰₯0.

  • πš„π™Ώ can be increased to any value β‰€πš‚π™΄πš€.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that belongs to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. does not belong to πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•) can be replaced by any other value in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• (resp. not in πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš•).

Usage

The πšŠπš–πš˜πš—πš_𝚜𝚎𝚚 constraint occurs in many timetabling problems. As a typical example taken from [HoevePesantRousseauSabharwal06], consider for instance a nurse -rostering problem where each nurse can work at most 2 night shifts during every period of 7 consecutive days.

Algorithm

Beldiceanu and CarlssonΒ [BeldiceanuCarlsson01] have proposed a first incomplete filtering algorithm for the πšŠπš–πš˜πš—πš_𝚜𝚎𝚚 constraint. Later on, W.-J.Β vanΒ Hoeve et al. proposed two filtering algorithmsΒ [HoevePesantRousseauSabharwal06] establishing arc-consistency as well as an incomplete filtering algorithm based on dynamic programming concepts. In 2007 Brand et al. came up with a reformulationΒ [BrandNarodytskaQuimperStuckeyWalsh07] that provides a complete filtering algorithm. One year later, Maher et al. use a reformulation in term of a linear programΒ [MaherNarodytskaQuimperWalsh08] where (1)Β each coefficient is an integer in {-1,0,1}, (2)Β each column has a block of consecutive 1's or -1's. From this reformulation they derive a flow model that leads to an algorithm that achieves a complete filtering in O(n 2 ) along a branch of the search tree.

Systems

sequence in Gecode, sequence in JaCoP.

See also

generalisation: πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš—Β (single set of values replaced by individual values).

part of system of constraints: πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™.

root concept: πšŠπš–πš˜πš—πš.

used in graph description: πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™.

Keywords

characteristic of a constraint: hypergraph.

combinatorial object: sequence.

constraint type: system of constraints, decomposition, sliding sequence constraint.

filtering: arc-consistency, linear programming, flow.

Arc input(s)

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

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—

Arc arity
πš‚π™΄πš€
Arc constraint(s)
πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™(π™»π™Ύπš†,πš„π™Ώ,πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—,πš…π™°π™»πš„π™΄πš‚)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1

Graph model

A constraint on sliding sequences of consecutive variables. Each vertex of the graph corresponds to a variable. Since they link πš‚π™΄πš€ variables, the arcs of the graph correspond to hyperarcs. In order to link πš‚π™΄πš€ consecutive variables we use the arc generator 𝑃𝐴𝑇𝐻. The constraint associated with an arc corresponds to the πšŠπš–πš˜πš—πš_πš•πš˜πš _πšžπš™ constraint defined at another entry of this catalogue.

Signature

Since we use the 𝑃𝐴𝑇𝐻 arc generator with an arity of πš‚π™΄πš€ on the items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection, the expression |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1 corresponds to the maximum number of arcs of the final graph. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂 = |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1 to 𝐍𝐀𝐑𝐂 β‰₯ |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.