5.300. soft_all_equal_min_ctr

DESCRIPTIONLINKSGRAPH
Origin

[HebrardSullivanRazgon08]

Constraint

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

Synonyms

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

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

Consider the equality constraints involving two distinct variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Among the previous set of constraints, 𝙽 is less than or equal to the number of equality constraints that hold.

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

Within the collection 〈5,1,5,5βŒͺ six equality constraints holds. Consequently, the 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πšŒπšπš› constraint holds since the argument 𝙽=6 is less than or equal to the number of equality constraints that hold.

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.

Remark

It was shown inΒ [HebrardSullivanRazgon08] that, finding out whether the 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πšŒπšπš› constraint has a solution or not is NP -hard. This was achieved by reduction from 3-dimensional-matching. Hebrard et al. also identify a tractable class when no value occurs in more than two variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ that is equivalent to the vertex matching problem. One year later,Β [HebrardMarxSullivanRazgon09] shows how to achieve bound-consistency in polynomial time.

See also

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

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

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

Keywords

complexity: 3-dimensional-matching.

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

filtering: 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. We use the arc generator πΆπΏπΌπ‘„π‘ˆπΈ(β‰ ) in order to avoid considering equality constraints between the same variable. The graph property states that 𝙽 is less than or equal to the number of equalities that hold in the final graph.

PartsΒ (A) andΒ (B) of FigureΒ 5.300.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. Six equality constraints remain in the final graph.

Figure 5.300.1. Initial and final graph of the 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŒπšπš› constraint
ctrs/soft_all_equal_min_ctrActrs/soft_all_equal_min_ctrB
(a) (b)