5.301. soft_all_equal_min_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 greater than or equal to the total number of variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection minus M (i.e., 𝙽 is greater 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 greater than or equal to the total number of variables 4 minus 3.

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.

Algorithm

Let m denote the total number of potential values that can be assigned to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. InΒ [HebrardMarxSullivanRazgon09], E.Β Hebrard et al. provides an O(m) filtering algorithm achieving arc-consistency on the 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŸπšŠπš› constraint. The same paper also provides an algorithm with a lower complexity for achieving range consistency. Both algorithms are based on the following ideas:

  • In a first phase, they both compute an envelope of the union π’Ÿ of the domains of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection, i.e.,Β an array A that indicates for each potential value v of π’Ÿ, the maximum number of variables that could possibly be assigned value v. Let π‘šπ‘Žπ‘₯_π‘œπ‘π‘ denote the maximum value over the entries of array A, and let 𝒱 π‘šπ‘Žπ‘₯ _π‘œπ‘π‘ denote the set of values which all occur in π‘šπ‘Žπ‘₯_π‘œπ‘π‘ variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. The quantity |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-π‘šπ‘Žπ‘₯_π‘œπ‘π‘ is a lower bound of 𝙽.

  • In a second phase, depending on the relative ordering between π‘šπ‘Žπ‘₯_π‘œπ‘π‘ and the minimum value of |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙽, i.e.,Β |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙽 Β―, we have the three following cases:

    1. When π‘šπ‘Žπ‘₯_π‘œπ‘π‘<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙽 Β―, the constraint 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŸπšŠπš› simply fails since not enough variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection can be assigned the same value.

    2. When π‘šπ‘Žπ‘₯_π‘œπ‘π‘=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙽 Β―, the constraint 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŸπšŠπš› can be satisfied. In this context, a value v can be removed from the domain of a variable V of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection if and only if:

      1. value v does not belong to 𝒱 π‘šπ‘Žπ‘₯ _π‘œπ‘π‘,

      2. the domain of variable V contains all values of 𝒱 π‘šπ‘Žπ‘₯ _π‘œπ‘π‘.

      On the one hand, the first condition can be understand as the fact that value v is not a value that allows to have at least |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙽 Β― variables assigned the same value. On the other hand, the second condition can be interpreted as the fact that variable V is absolutely required in order to have at least |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙽 Β― variables assigned the same value.

    3. When π‘šπ‘Žπ‘₯_π‘œπ‘π‘>|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙽 Β―, the constraint 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŸπšŠπš› can be satisfied, but no value can be pruned.

Note that, in the context of range consistency, the first phase of the filtering algorithm can be interpreted as a sweep algorithm were:

  • On the one hand, the sweep status corresponds to the maximum number of occurrence of variables that can be assigned a given value.

  • On the other hand, the event point series correspond to the minimum values of the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection as well as to the maximum valuesΒ (+1) of the same variables.

Figure 5.301.1. Illustration of the two phases filtering algorithm
ctrs/soft_all_equal_min_var1

FigureΒ 5.301.1 illustrates the previous filtering algorithm on an example where 𝙽 is equal to 1, and where we have four variables V 1 , V 2 , V 3 and V 4 respectively taking their values within intervals [1,3], [3,7], [0,8] and [5,6] (see PartΒ (A) of FigureΒ 5.301.1, where the values of each variable are assigned a same colour that we retrieve in the other parts of FigureΒ 5.301.1).

PartΒ (B) of FigureΒ 5.301.1 illustrates the first phase of the filtering algorithm, namely the computation of the envelope of the domains of variables V 1 , V 2 , V 3 and V 4 . The start events s 1 , s 2 , s 3 , s 4 (i.e.,Β the events respectively associated with the minimum value of variables V 1 , V 2 , V 3 , V 4 ) where the envelope is increased by 1 are represented by the character ↑. Similarly, the end events (i.e.,Β the events e 1 , e 2 , e 3 , e 4 respectively associated with the maximum valueΒ (+1) of V 1 , V 2 , V 3 , V 4 are represented by the character ↓). Since the highest peak of the envelope is equal to 3 we have that π‘šπ‘Žπ‘₯_π‘œπ‘π‘ is equal to 3. The values that allow to reach this highest peak are equal to 𝒱 π‘šπ‘Žπ‘₯ _π‘œπ‘π‘={3,5,6} (i.e.,Β shown in red in PartΒ (B) of FigureΒ 5.301.1).

Finally, PartΒ (C) of FigureΒ 5.301.1 illustrates the second phase of the filtering algorithm. Since π‘šπ‘Žπ‘₯_π‘œπ‘π‘=3 is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-𝙽 Β―=4-1 we remove from the variables whose domains contain 𝒱 π‘šπ‘Žπ‘₯ _π‘œπ‘π‘={3,5,6} (i.e.,Β variables V 2 and V 3 ) all values not in 𝒱 π‘šπ‘Žπ‘₯ _π‘œπ‘π‘={3,5,6} (i.e.,Β values 4, 7 for variable V 2 and values 0, 1, 2, 4, 7, 8 for variable V 3 ).

See also

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

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

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

Keywords

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

filtering: arc-consistency, sweep.

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 greater 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.301.2 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.301.2. Initial and final graph of the 𝚜𝚘𝚏𝚝_πšŠπš•πš•_πšŽπššπšžπšŠπš•_πš–πš’πš—_πšŸπšŠπš› constraint
ctrs/soft_all_equal_min_varActrs/soft_all_equal_min_varB
(a) (b)