5.36. balance

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

N.Β Beldiceanu

Constraint

πš‹πšŠπš•πšŠπš—πšŒπšŽ(𝙱𝙰𝙻𝙰𝙽𝙲𝙴,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™±π™°π™»π™°π™½π™²π™΄πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
𝙱𝙰𝙻𝙰𝙽𝙲𝙴β‰₯0
π™±π™°π™»π™°π™½π™²π™΄β‰€πš–πšŠπš‘(0,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-2)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

𝙱𝙰𝙻𝙰𝙽𝙲𝙴 is equal to the difference between the number of occurrence of the value that occurs the most and the value that occurs the least within the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

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

In this example, values 1,3 and 7 are respectively used 3,1 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). FigureΒ 5.36.1 shows the solution associated with the example.

Figure 5.36.1. Illustration of the example: five variables respectively fixed to values 3, 1, 7, 1 and 1, and the corresponding value of 𝙱𝙰𝙻𝙰𝙽𝙲𝙴=2
ctrs/balance1
Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

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

Usage

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

Remark

If we do not want to use an automaton with an array of counters a possible reformulation of the πš‹πšŠπš•πšŠπš—πšŒπšŽ constraint can be achieved in the following way. We use a πšœπš˜πš›πš constraint in order to reorder the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and compute the difference between the longest and the smallest sequences of consecutive values.

See also

generalisation: πš‹πšŠπš•πšŠπš—πšŒπšŽ_πš’πš—πšπšŽπš›πšŸπšŠπš•Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ/πšŒπš˜πš—πšœπšπšŠπš—πš), πš‹πšŠπš•πšŠπš—πšŒπšŽ_πš–πš˜πšπšžπš•πš˜Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ mod πšŒπš˜πš—πšœπšπšŠπš—πš), πš‹πšŠπš•πšŠπš—πšŒπšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš™πšŠπš›πšπš’πšπš’πš˜πš—).

related: πšπš›πšŽπšŽ_πš›πšŠπš—πšπšŽΒ (balanced assignment versus balanced tree).

Keywords

application area: assignment.

characteristic of a constraint: 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.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ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.36.2 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.36.2. Initial and final graph of the πš‹πšŠπš•πšŠπš—πšŒπšŽ constraint
ctrs/balanceActrs/balanceB
(a) (b)
Automaton

FigureΒ 5.36.3 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.36.3. Automaton of the πš‹πšŠπš•πšŠπš—πšŒπšŽ constraint
ctrs/balance2