5.303. soft_alldifferent_var

DESCRIPTIONLINKSGRAPH
Origin

[PetitReginBessiere01]

Constraint

𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŸπšŠπš›(𝙲,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Synonyms

𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπš_πšŸπšŠπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πšŸπšŠπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπš_πš–πš’πš—_πšŸπšŠπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš–πš’πš—_πšŸπšŠπš›, 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πš–πš’πš—_πšŸπšŠπš›.

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

𝙲 is greater than or equal to the minimum number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ for which the value needs to be changed in order that all variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ take a distinct value.

Example
3,πšŸπšŠπš›-5,πšŸπšŠπš›-1,πšŸπšŠπš›-9,πšŸπšŠπš›-1,πšŸπšŠπš›-5,πšŸπšŠπš›-5

Within the collection 〈5,1,9,1,5,5βŒͺ, 3 and 2 items are respectively fixed to values 5 and 1. Therefore one must change the values of at least (3-1)+(2-1)=3 items to get back to 6 distinct values. Consequently, the 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŸπšŠπš› constraint holds since its first argument 𝙲 is greater than or equal to 3.

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

A soft πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint.

Remark

Since it focus on the soft aspect of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint, the original articleΒ [PetitReginBessiere01], which introduce this constraint, describes how to evaluate the minimum value of 𝙲 and how to prune according to the maximum value of 𝙲.

The 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŸπšŠπš› constraint is called 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπš_πš–πš’πš—_πšŸπšŠπš› inΒ [HebrardMarxSullivanRazgon09].

Algorithm

The filtering algorithm presented inΒ [PetitReginBessiere01] achieves arc-consistency.

Reformulation

By introducing a variable M that gives the number of distinct values used by variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, the 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŸπšŠπš›(𝙲,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) constraint can be expressed as a conjunction of the πš—πšŸπšŠπš•πšžπšŽ(M,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) constraint and of the linear constraint 𝙲β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-M.

See also

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

hard version: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

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

Keywords

characteristic of a constraint: all different, disequality.

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

final graph structure: strongly connected component, equivalence.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐒𝐂𝐂β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙲

Graph model

We generate a clique with binary equalities constraints between each pairs of vertices (this include an arc between a vertex and itself) and we state that 𝙲 is equal to the difference between the total number of variables and the number of strongly connected components.

PartsΒ (A) andΒ (B) of FigureΒ 5.303.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐒𝐂𝐂 graph property we show the different strongly connected components of the final graph. Each strongly connected component of the final graph includes all variables that take the same value. Since we have 6 variables and 3 strongly connected components the cost variable 𝙲 is greater than or equal to 6-3.

Figure 5.303.1. Initial and final graph of the 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŸπšŠπš› constraint
ctrs/soft_alldifferent_varActrs/soft_alldifferent_varB
(a) (b)