5.43. 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)
(0,3,3,1,1,1,3)
(4,3,1,1,1,1,1)

In the first example, values 1,3 and 7 are respectively used 3,1 and 1 times. The corresponding πš‹πšŠπš•πšŠπš—πšŒπšŽ 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.43.1 shows the solution associated with this first example.

Figure 5.43.1. Illustration of the first example of the Example slot: five variables V 1 , V 2 , V 3 , V 4 , V 5 respectively fixed to values 3, 1, 7, 1 and 1, and the corresponding value of 𝙱𝙰𝙻𝙰𝙽𝙲𝙴=2
ctrs/balance-1-tikz
All solutions

FigureΒ 5.43.2 gives all solutions to the following non ground instance of the πš‹πšŠπš•πšŠπš—πšŒπšŽ constraint: π™±π™°π™»π™°π™½π™²π™΄βˆˆ[2,3], V 1 ∈[0,5], V 2 ∈[2,6], V 3 ∈[0,1], V 4 ∈[1,2], πš‹πšŠπš•πšŠπš—πšŒπšŽ(𝙱𝙰𝙻𝙰𝙽𝙲𝙴,〈V 1 ,V 2 ,V 3 ,V 4 βŒͺ).

Figure 5.43.2. All solutions corresponding to the non ground example of the πš‹πšŠπš•πšŠπš—πšŒπšŽ constraint of the All solutions slot
ctrs/balance-2-tikz
Typical
𝙱𝙰𝙻𝙰𝙽𝙲𝙴≀2+|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|/10
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>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.

Arg. properties

Functional dependency: 𝙱𝙰𝙻𝙰𝙽𝙲𝙴 determined by πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

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.

Counting
Length (n)2345678
Solutions9646257776117649209715243046721

Number of solutions for πš‹πšŠπš•πšŠπš—πšŒπšŽ: domains 0..n

ctrs/balance-3-tikz

ctrs/balance-4-tikz

Length (n)2345678
Total9646257776117649209715243046721
Parameter
value

0928185726861740328682929
1-36360570075600134260024272640
2--8012003003061152015350832
3---1503150952562469600
4----2527056256032
5-----39214112
6------576

Solution count for πš‹πšŠπš•πšŠπš—πšŒπšŽ: domains 0..n

ctrs/balance-5-tikz

ctrs/balance-6-tikz

See also

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

implies: 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŒπšπš›.

related: πš‹πšŠπš•πšŠπš—πšŒπšŽ_πšŒπš’πšŒπš•πšŽΒ (balanced assignment versus graph partitionning with balanced cycles), πš‹πšŠπš•πšŠπš—πšŒπšŽ_πš™πšŠπšπš‘Β (balanced assignment versus graph partitionning with balanced paths), πš‹πšŠπš•πšŠπš—πšŒπšŽ_πšπš›πšŽπšŽΒ (balanced assignment versus graph partitionning with balanced trees), πš—πšŸπšŠπš•πšžπšŽΒ (no restriction on how balanced an assignment is), πšπš›πšŽπšŽ_πš›πšŠπš—πšπšŽΒ (balanced assignment versus balanced tree).

shift of concept: πšŽπššπšžπš’πš•πš’πš‹πš›πš’πšžπš–.

Keywords

application area: assignment.

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

constraint arguments: pure functional dependency.

constraint type: value constraint.

final graph structure: equivalence.

modelling: balanced assignment, functional dependency.

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.43.3 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the 𝐑𝐀𝐍𝐆𝐄_𝐍𝐒𝐂𝐂 graph property, we show the largest and smallest strongly connected components of the final graph.

Figure 5.43.3. Initial and final graph of the πš‹πšŠπš•πšŠπš—πšŒπšŽ constraint
ctrs/balanceActrs/balanceB
(a) (b)
Automaton

FigureΒ 5.43.4 depicts the automaton associated with the πš‹πšŠπš•πšŠπš—πšŒπšŽ constraint. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable S i that is equal to 1.

Figure 5.43.4. Automaton of the πš‹πšŠπš•πšŠπš—πšŒπšŽ constraint
ctrs/balance-7-tikz