5.37. balance_interval

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ.

Constraint

๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•(๐™ฑ๐™ฐ๐™ป๐™ฐ๐™ฝ๐™ฒ๐™ด,๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚,๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป)

Arguments
๐™ฑ๐™ฐ๐™ป๐™ฐ๐™ฝ๐™ฒ๐™ด๐š๐šŸ๐šŠ๐š›
๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐šŸ๐šŠ๐š›-๐š๐šŸ๐šŠ๐š›)
๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป๐š’๐š—๐š
Restrictions
๐™ฑ๐™ฐ๐™ป๐™ฐ๐™ฝ๐™ฒ๐™ดโ‰ฅ0
๐™ฑ๐™ฐ๐™ป๐™ฐ๐™ฝ๐™ฒ๐™ดโ‰ค๐š–๐šŠ๐šก(0,|๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚|-2)
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚,๐šŸ๐šŠ๐š›)
๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป>0
Purpose

Consider the largest set ๐’ฎ 1 (respectively the smallest set ๐’ฎ 2 ) of variables of the collection ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚ that take their value in a same interval [๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ปยทk,๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ปยทk+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1], where k is an integer. ๐™ฑ๐™ฐ๐™ป๐™ฐ๐™ฝ๐™ฒ๐™ด is equal to the difference between the cardinality of ๐’ฎ 2 and the cardinality of ๐’ฎ 1 .

Example
(3,6,4,3,3,4,3)

In the example, the third argument ๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป=3 defines the following family of intervals [3ยทk,3ยทk+2], where k is an integer. Values 6,4,3,3 and 4 are respectively located within intervals [6,8], [3,5], [3,5], [3,5] and [3,5]. Therefore intervals [6,8] and [3,5] are respectively used 1 and 4 times. The ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š• constraint holds since its first argument ๐™ฑ๐™ฐ๐™ป๐™ฐ๐™ฝ๐™ฒ๐™ด is assigned to the difference between the maximum and minimum number of the previous occurrences (i.e.,ย 4-1).

Typical
|๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚|>2
๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป>1
Symmetries
  • Items of ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚ are permutable.

  • An occurrence of a value of ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š› that belongs to the k-th interval, of size ๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป, can be replaced by any other value of the same interval.

Usage

An application of the ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š• constraint is to enforce a balanced assignment of interval of values, no matter how many distinct interval of values will be used. In this case one will push down the maximum value of the first argument of the ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š• constraint.

See also

specialisation: ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽย (๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ/๐šŒ๐š˜๐š—๐šœ๐š๐šŠ๐š—๐š replaced by ๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ).

Keywords

application area: assignment.

characteristic of a constraint: automaton, automaton with array of counters.

constraint type: value constraint.

final graph structure: equivalence.

modelling: interval, balanced assignment.

Arc input(s)

๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚

Arc generator
๐ถ๐ฟ๐ผ๐‘„๐‘ˆ๐ธโ†ฆ๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ1,๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ2)

Arc arity
Arc constraint(s)
๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ1.๐šŸ๐šŠ๐š›/๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป=๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ2.๐šŸ๐šŠ๐š›/๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป
Graph property(ies)
๐‘๐€๐๐†๐„_๐๐’๐‚๐‚=๐™ฑ๐™ฐ๐™ป๐™ฐ๐™ฝ๐™ฒ๐™ด

Graph class
๐™ด๐š€๐š„๐™ธ๐š…๐™ฐ๐™ป๐™ด๐™ฝ๐™ฒ๐™ด

Graph model

The graph property ๐‘๐€๐๐†๐„_๐๐’๐‚๐‚ constraints the difference between the sizes of the largest and smallest strongly connected components.

Partsย (A) andย (B) of Figureย 5.37.1 respectively show the initial and final graph associated with the Example slot. Since we use the ๐‘๐€๐๐†๐„_๐๐’๐‚๐‚ graph property, we show the largest and smallest strongly connected components of the final graph.

Figure 5.37.1. Initial and final graph of the ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š• constraint
ctrs/balance_intervalActrs/balance_intervalB
(a) (b)
Automaton

Figureย 5.37.2 depicts the automaton associated with the ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š• constraint. To each item of the collection ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚ corresponds a signature variable ๐š‚ i that is equal to 1.

Figure 5.37.2. Automaton of the ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š• constraint
ctrs/balance_interval1