5.299. soft_all_equal_max_var

DESCRIPTIONLINKSGRAPH
Origin

[HebrardMarxSullivanRazgon09]

Constraint

𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πšŠπš‘_πšŸπšŠπš›(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™½πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
𝙽β‰₯0
𝙽≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

Let M be the number of occurrences of the most often assigned value to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. 𝙽 is less than or equal to the total number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection minus M (i.e., 𝙽 is less than or equal to the minimum number of variables that need to be reassigned in order to obtain a solution where all variables are assigned a same value).

Example
(1,5,1,5,5)

Within the collection 〈5,1,5,5βŒͺ, 3 is the number of occurrences of the most assigned value. Consequently, the 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πšŠπš‘_πšŸπšŠπš› constraint holds since the argument 𝙽=1 is less than or equal to the total number of variables 4 minus 3.

Symmetries
  • 𝙽 can be decreased to any value β‰₯0.

  • 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.

Algorithm

[HebrardMarxSullivanRazgon09].

See also

common keyword: 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŒπšπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŸπšŠπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπšπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŸπšŠπš›Β (soft constraint).

hard version: πšŠπš•πš•_πšŽπššπšžπšŠπš•.

related: πšŠπšπš–πš˜πšœπš_πš—πšŸπšŠπš•πšžπšŽ.

Keywords

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

filtering: arc-consistency, bound-consistency.

Arc input(s)

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

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
πŒπ€π—_𝐍𝐒𝐂𝐂≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙽

Graph model

We generate an initial graph with binary equalities constraints between each vertex and its successors. The graph property states that 𝙽 is less than or equal to the difference between the total number of vertices of the initial graph and the number of vertices of the largest strongly connected component of the final graph.

PartsΒ (A) andΒ (B) of FigureΒ 5.299.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_𝐍𝐒𝐂𝐂 graph property we show one of the largest strongly connected component of the final graph.

Figure 5.299.1. Initial and final graph of the 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πšŠπš‘_πšŸπšŠπš› constraint
ctrs/soft_all_equal_max_varActrs/soft_all_equal_max_varB
(a) (b)