Global Constraint Catalog: Csoft_same

5.308. soft_same_var

DESCRIPTION

LINKS

GRAPH

Origin

[vanHoeve05]

Constraint

$𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚟𝚊𝚛 (𝙲, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$

Synonym

$𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎$ .

Arguments

$𝙲$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝙲 \geq 0

𝙲 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2, 𝚟𝚊𝚛)

Purpose

$𝙲$ is the minimum number of values to change in the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collections so that the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collection correspond to the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ collection according to a permutation.

Example

(\begin{matrix} 4, 〈\begin{matrix} 𝚟𝚊𝚛 - 9, \\ 𝚟𝚊𝚛 - 9, \\ 𝚟𝚊𝚛 - 9, \\ 𝚟𝚊𝚛 - 9, \\ 𝚟𝚊𝚛 - 9, \\ 𝚟𝚊𝚛 - 1 \end{matrix}〉, \\ 〈\begin{matrix} 𝚟𝚊𝚛 - 9, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 8 \end{matrix}〉 \end{matrix})

As illustrated by Figure 5.308.1, there is a correspondence between two pairs of values of the collections $〈 9, 9, 9, 9, 9, 1 〉$ and $〈 9, 1, 1, 1, 1, 8 〉$ . Consequently, we must unset at least $6 - 2$ items (6 is the number of items of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collections). The $𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚟𝚊𝚛$ constraint holds since its first argument $𝙲$ is set to $6 - 2$ .

Figure 5.308.1. Correspondence between collection $〈 9, 9, 9, 9, 9, 1 〉$ and collection $〈 9, 1, 1, 1, 1, 8 〉$

Symmetries

Arguments are permutable w.r.t. permutation $(𝙲)$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ are permutable.
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ are permutable.
All occurrences of two distinct values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be swapped; all occurrences of a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be renamed to any unused value.

Usage

A soft $𝚜𝚊𝚖𝚎$ constraint.

Algorithm

[vanHoeve05].

See also

hard version: $𝚜𝚊𝚖𝚎$ .

implies: $𝚜𝚘𝚏𝚝_𝚞𝚜𝚎𝚍_𝚋𝚢_𝚟𝚊𝚛$ .

Keywords

constraint arguments: constraint between two collections of variables.

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

filtering: minimum cost flow.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 = 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐒𝐈𝐍𝐊_𝐍𝐒𝐎𝐔𝐑𝐂𝐄

= | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | - 𝙲

Graph model

Parts (A) and (B) of Figure 5.308.2 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐒𝐈𝐍𝐊_𝐍𝐒𝐎𝐔𝐑𝐂𝐄$ graph property, the source and sink vertices of the final graph are stressed with a double circle. The $𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚟𝚊𝚛$ constraint holds since the cost 4 corresponds to the difference between the number of variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and the sum over the different connected components of the minimum number of sources and sinks.

Figure 5.308.2. Initial and final graph of the $𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚟𝚊𝚛$ constraint

(a)

(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.308. soft_same_var

Figure 5.308.1. Correspondence between collection $〈 9, 9, 9, 9, 9, 1 〉$ and collection $〈 9, 1, 1, 1, 1, 8 〉$

Figure 5.308.2. Initial and final graph of the $𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚟𝚊𝚛$ constraint

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

5. Global Constraint Catalogue

5.308. soft_same_var

Figure 5.308.1. Correspondence between collection 〈9,9,9,9,9,1〉 and collection 〈9,1,1,1,1,8〉

Figure 5.308.2. Initial and final graph of the 𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚟𝚊𝚛 constraint

W3C: XHTML - last update: 2010-12-6. SD.

Figure 5.308.1. Correspondence between collection $〈 9, 9, 9, 9, 9, 1 〉$ and collection $〈 9, 1, 1, 1, 1, 8 〉$

Figure 5.308.2. Initial and final graph of the $𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚟𝚊𝚛$ constraint