5.302. soft_alldifferent_ctr

DESCRIPTIONLINKSGRAPH
Origin

[PetitReginBessiere01]

Constraint

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

Synonyms

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

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

Consider the disequality constraints involving two distinct variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[i].πšŸπšŠπš› and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚[j].πšŸπšŠπš› (i<j) of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Among the previous set of constraints, 𝙲 is greater than or equal to the number of disequality constraints that do not hold.

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

Within the collection 〈5,1,9,1,5,5βŒͺ the first and fifth values, the first and sixth values, the second and fourth values, and the fifth and sixth values are identical. Consequently, the argument 𝙲=4 is greater than or equal to the number of disequality constraints that do not hold (i.e,Β 4) and the 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπšπš› constraint holds.

Symmetries
  • 𝙲 can be increased.

  • 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

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

Algorithm

Since it focus on the soft aspect of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint, the original articleΒ [PetitReginBessiere01] that introduces this constraint describes how to evaluate the minimum value of 𝙲 and how to prune according to the maximum value of 𝙲. The corresponding filtering algorithm does not achieve arc-consistency. W.-J.Β vanΒ HoeveΒ [Hoeve04] presents a new filtering algorithm that achieves arc-consistency. This algorithm is based on a reformulation into a minimum -cost flow problem.

See also

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

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

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

Keywords

characteristic of a constraint: all different, disequality.

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

filtering: minimum cost flow.

modelling: degree of diversity of a set of solutions.

modelling exercises: degree of diversity of a set of solutions.

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. We use the arc generator πΆπΏπΌπ‘„π‘ˆπΈ(<) in order to avoid counting twice the same equality constraint. The graph property states that 𝙲 is greater than or equal to the number of equalities that hold in the final graph.

PartsΒ (A) andΒ (B) of FigureΒ 5.302.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold. Since four equality constraints remain in the final graph the cost variable 𝙲 is greater than or equal to 4.

Figure 5.302.1. Initial and final graph of the 𝚜𝚘𝚏𝚝_πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πšŒπšπš› constraint
ctrs/soft_alldifferent_ctrActrs/soft_alldifferent_ctrB
(a) (b)