5.39. balance_partition

DESCRIPTIONLINKSGRAPH
Origin

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

Constraint

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

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

Consider the largest set ๐’ฎ 1 (respectively the smallest set ๐’ฎ 2 ) of variables of the collection ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚ that take their value in the same partition of the collection ๐™ฟ๐™ฐ๐š๐šƒ๐™ธ๐šƒ๐™ธ๐™พ๐™ฝ๐š‚.๐™ฑ๐™ฐ๐™ป๐™ฐ๐™ฝ๐™ฒ๐™ด is equal to the difference between the cardinality of ๐’ฎ 2 and the cardinality of ๐’ฎ 1 .

Example
1,6,2,6,4,4,๐š™-1,3,๐š™-4,๐š™-2,6

In this example values 6,2,6,4,4 are respectively associated with the partitions ๐š™-โŒฉ2,6โŒช and ๐š™-โŒฉ4โŒช. Partitions ๐š™-โŒฉ4โŒช and ๐š™-โŒฉ2,6โŒช are respectively used 2 and 3 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-2). Note that we do not consider those partitions that are not used at all.

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

  • Items of ๐™ฟ๐™ฐ๐š๐šƒ๐™ธ๐šƒ๐™ธ๐™พ๐™ฝ๐š‚ are permutable.

  • Items of ๐™ฟ๐™ฐ๐š๐šƒ๐™ธ๐šƒ๐™ธ๐™พ๐™ฝ๐š‚.๐š™ are permutable.

  • An occurrence of a value of ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š› can be replaced by any other value that also belongs to the same partition of ๐™ฟ๐™ฐ๐š๐šƒ๐™ธ๐šƒ๐™ธ๐™พ๐™ฝ๐š‚.

Usage

An application of the ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š™๐šŠ๐š›๐š๐š’๐š๐š’๐š˜๐š— is to enforce a balanced assignment of values, no matter how many distinct partitions 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 ๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ).

used in graph description: ๐š’๐š—_๐šœ๐šŠ๐š–๐šŽ_๐š™๐šŠ๐š›๐š๐š’๐š๐š’๐š˜๐š—.

Keywords

application area: assignment.

characteristic of a constraint: partition.

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.39.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.39.1. Initial and final graph of the ๐š‹๐šŠ๐š•๐šŠ๐š—๐šŒ๐šŽ_๐š™๐šŠ๐š›๐š๐š’๐š๐š’๐š˜๐š— constraint
ctrs/balance_partitionActrs/balance_partitionB
(a) (b)