5.364. soft_same_partition_var

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—

Constraint

𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—_πšŸπšŠπš›(𝙲,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚)

Synonym

𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—.

Type
πš…π™°π™»πš„π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•-πš’πš—πš)
Arguments
π™²πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš™-πš…π™°π™»πš„π™΄πš‚)
Restrictions
𝙲β‰₯0
𝙲≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚,πš™)
|π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚|β‰₯2
|πš…π™°π™»πš„π™΄πš‚|β‰₯1
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
πšπš’πšœπšπš’πš—πšŒπš(πš…π™°π™»πš„π™΄πš‚,πšŸπšŠπš•)
Purpose

For each integer i in [1,|π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚|], let 𝑁1 i (respectively 𝑁2 i ) denote the number of variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 (respectively πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) that take their value in the i th partition of the collection π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚. 𝙲 is the minimum number of values to change in the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections so that for all i in [1,|π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚|] we have 𝑁1 i =𝑁2 i .

Example
4,9,9,9,9,9,1,9,1,1,1,1,8,πš™-1,2,πš™-9,πš™-7,8

In the example, the values of the collections 〈9,9,9,9,9,1βŒͺ and 〈9,1,1,1,1,8βŒͺ are respectively associated with the partitions πš™-〈9βŒͺ, πš™-〈9βŒͺ, πš™-〈9βŒͺ, πš™-〈9βŒͺ, πš™-〈9βŒͺ, πš™-〈1,2βŒͺ and πš™-〈9βŒͺ, πš™-〈1,2βŒͺ, πš™-〈1,2βŒͺ, πš™-〈1,2βŒͺ, πš™-〈1,2βŒͺ, πš™-〈7,8βŒͺ. Since there is a correspondence between two pairs of partitions we must unset at least 6-2 items (6 is the number of items of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collections). Consequently, the 𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—_πšŸπšŠπš› constraint holds since its first argument 𝙲 is set to 6-2.

Typical
𝙲>0
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš›)>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš›)>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|>|π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚|
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|>|π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚|
Symmetries
  • Arguments are permutable w.r.t. permutation (𝙲) (πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2) (π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚).

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 are permutable.

  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 are permutable.

  • Items of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚ are permutable.

  • Items of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚.πš™ are permutable.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1.πšŸπšŠπš› can be replaced by any other value that also belongs to the same partition of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2.πšŸπšŠπš› can be replaced by any other value that also belongs to the same partition of π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚.

Usage

A soft πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš— constraint.

Algorithm

See algorithm of the 𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πšŸπšŠπš› constraint.

See also

hard version: πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—.

implies: 𝚜𝚘𝚏𝚝_𝚞𝚜𝚎𝚍_πš‹πš’_πš™πšŠπš›πšπš’πšπš’πš˜πš—_πšŸπšŠπš›.

Keywords

characteristic of a constraint: partition.

constraint arguments: constraint between two collections of variables.

constraint type: soft constraint, relaxation, variable-based violation measure.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πš’πš—_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›,π™Ώπ™°πšπšƒπ™Έπšƒπ™Έπ™Ύπ™½πš‚)
Graph property(ies)
ππ’πˆππŠ_ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|-𝙲

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.364.1 respectively show the initial and final graph associated with the Example slot. Since we use the ππ’πˆππŠ_ππ’πŽπ”π‘π‚π„ graph property, the source and sink vertices of the final graph are stressed with a double circle. The 𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—_πšŸπšŠπš› constraint holds since the cost 4 corresponds to the difference between the number of variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and the sum over the different connected components of the minimum number of sources and sinks.

Figure 5.364.1. Initial and final graph of the 𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—_πšŸπšŠπš› constraint
ctrs/soft_same_partition_varA
(a)
ctrs/soft_same_partition_varB
(b)