5.350. sliding_distribution

DESCRIPTIONLINKSGRAPH
Origin

[ReginPuget97]

Constraint

πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš—(πš‚π™΄πš€,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš…π™°π™»πš„π™΄πš‚)

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

For each sequence of πš‚π™΄πš€ consecutive variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection, each value πš…π™°π™»πš„π™΄πš‚[i].πšŸπšŠπš• (1≀i≀|πš…π™°π™»πš„π™΄πš‚|) should be taken by at least πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πš’πš— and at most πš…π™°π™»πš„π™΄πš‚[i].πš˜πš–πšŠπš‘ variables.

Example
4,0,5,0,6,5,0,0,πšŸπšŠπš•-0πš˜πš–πš’πš—-1πš˜πš–πšŠπš‘-2,πšŸπšŠπš•-1πš˜πš–πš’πš—-0πš˜πš–πšŠπš‘-4,πšŸπšŠπš•-4πš˜πš–πš’πš—-0πš˜πš–πšŠπš‘-4,πšŸπšŠπš•-5πš˜πš–πš’πš—-1πš˜πš–πšŠπš‘-2,πšŸπšŠπš•-6πš˜πš–πš’πš—-0πš˜πš–πšŠπš‘-2

The πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš— constraint holds since:

  • On the first sequence of 4 consecutive values 0 5 0 6 values 0, 1, 4, 5 and 6 are respectively used 2, 0, 0, 1 and 1 times.

  • On the second sequence of 4 consecutive values 5 0 6 5 values 0, 1, 4, 5 and 6 are respectively used 1, 0, 0, 2 and 1 times.

  • On the third sequence of 4 consecutive values 0 6 5 0 values 0, 1, 4, 5 and 6 are respectively used 2, 0, 0, 1 and 1 times.

  • On the fourth sequence of 4 consecutive values 6 5 0 0 values 0, 1, 4, 5 and 6 are respectively used 2, 0, 0, 1 and 1 times.

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

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

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

  • πš…π™°π™»πš„π™΄πš‚.πš˜πš–πš’πš— can be decreased to any value β‰₯0.

  • πš…π™°π™»πš„π™΄πš‚.πš˜πš–πšŠπš‘ can be increased to any value β‰€πš‚π™΄πš€.

  • All occurrences of two distinct values in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› or πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• can be swapped; all occurrences of a value in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› or πš…π™°π™»πš„π™΄πš‚.πšŸπšŠπš• can be renamed to any unused value.

Arg. properties
  • Contractible wrt. πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ when πš‚π™΄πš€=1.

  • Prefix-contractible wrt. πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

  • Suffix-contractible wrt. πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

  • Contractible wrt. πš…π™°π™»πš„π™΄πš‚.

See also

common keyword: πš™πšŠπšπšπšŽπš›πš—, πšœπš•πš’πšπš’πš—πš_πšœπšžπš–, πšœπšπš›πšŽπšπšŒπš‘_πšŒπš’πš›πšŒπšžπš’πš, πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘Β (sliding sequence constraint).

part of system of constraints: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™.

specialisation: πšŠπš–πš˜πš—πš_𝚜𝚎𝚚 (individual values replaced by single set of values).

used in graph description: πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™.

Keywords

characteristic of a constraint: hypergraph.

combinatorial object: sequence.

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

Arc input(s)

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

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

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

Graph model

Note that the πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš— constraint is a constraint where the arc constraints do not have an arity of 2.

PartsΒ (A) andΒ (B) of FigureΒ 5.350.1 respectively show the initial and final graph associated with the Example slot. Since all arc constraints hold (i.e.,Β because of the graph property 𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πš‚π™΄πš€+1) the final graph corresponds to the initial graph.

Figure 5.350.1. (A)Β Initial and (B)Β final graph of the πšœπš•πš’πšπš’πš—πš_πšπš’πšœπšπš›πš’πš‹πšžπšπš’πš˜πš—(4,〈0,5,0,6,5,0,0βŒͺ,〈0 1 2, 1 0 4, 4 0 4, 5 1 2, 6 0 2βŒͺ) constraint of the Example slot where each ellipse represents an hyperedge involving πš‚π™΄πš€=4 vertices (to each ellipse corresponds a πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ constraint)
ctrs/sliding_distribution-1-tikz