5.38. balance_modulo

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 have the same remainder when divided by ๐™ผ. ๐™ฑ๐™ฐ๐™ป๐™ฐ๐™ฝ๐™ฒ๐™ด is equal to the difference between the cardinality of ๐’ฎ 2 and the cardinality of ๐’ฎ 1 .

Example
(2,6,1,7,1,5,3)

In this example values 6, 1, 7, 1, 5 are respectively associated with the equivalence classes 6 mod 3=0, 1 mod 3=1, 7 mod 3=1, 1 mod 3=1, 5 mod 3=2. Therefore the equivalence classes 0, 1 and 2 are respectively used 1, 3 and 1 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.,ย 3-1).

Typical
|๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚|>2
๐™ผ>1
๐™ผ<๐š–๐šŠ๐šก๐šŸ๐šŠ๐š•(๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›)
Symmetries
  • Items of ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚ are permutable.

  • An occurrence of a value u of ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š› can be replaced by any other value v such that v is congruent to u modulo ๐™ผ.

Usage

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

See also

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

Keywords

application area: assignment.

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

constraint type: value constraint.

final graph structure: equivalence.

modelling: balanced assignment.

Arc input(s)

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

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

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

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

Graph model

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

Partsย (A) andย (B) of Figureย 5.38.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.38.1. Initial and final graph of the ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š–๐š˜๐š๐šž๐š•๐š˜ constraint
ctrs/balance_moduloActrs/balance_moduloB
(a) (b)
Automaton

Figureย 5.38.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.38.2. Automaton of the ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š–๐š˜๐š๐šž๐š•๐š˜ constraint
ctrs/balance_modulo1