Global Constraint Catalog: Csoft_same_modulo

5.363. soft_same_modulo_var

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$

Constraint

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

Synonym

$𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ .

Arguments

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

Restrictions

𝙲 \geq 0

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

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝙼 > 0

Purpose

For each integer $R$ in $[0, 𝙼 - 1]$ , let $𝑁 1_{R}$ (respectively $𝑁 2_{R}$ ) denote the number of variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ (respectively $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ ) that have $R$ as a rest when divided by $𝙼$ . $𝙲$ is the minimum number of values to change in the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collections so that for all $R$ in $[0, 𝙼 - 1]$ we have $𝑁 1_{R} = 𝑁 2_{R}$ .

Example

(4, 〈9, 9, 9, 9, 9, 1〉, 〈9, 1, 1, 1, 1, 8〉, 3)

In the example, the values of the collections $〈 9, 9, 9, 9, 9, 1 〉$ and $〈 9, 1, 1, 1, 1, 8 〉$ are respectively associated with the equivalence classes $9 \mod 3 = 0$ , $9 \mod 3 = 0$ , $9 \mod 3 = 0$ , $9 \mod 3 = 0$ , $9 \mod 3 = 0$ , $1 \mod 3 = 1$ and $9 \mod 3 = 0$ , $1 \mod 3 = 1$ , $1 \mod 3 = 1$ , $1 \mod 3 = 1$ , $1 \mod 3 = 1$ , $8 \mod 3 = 2$ . Since there is a correspondence between two pairs of equivalence classes we must unset at least $6 - 2$ items (6 is the number of items of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collections). Consequently, the $𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘_𝚟𝚊𝚛$ constraint holds since its first argument $𝙲$ is set to $6 - 2$ .

Typical

𝙲 > 0

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | > 1

𝚛𝚊𝚗𝚐𝚎

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

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛) > 1

𝙼 > 1

𝙼 <

𝚖𝚊𝚡𝚟𝚊𝚕

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

𝙼 <

𝚖𝚊𝚡𝚟𝚊𝚕

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

Symmetries

Arguments are permutable w.r.t. permutation $(𝙲)$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ $(𝙼)$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ are permutable.
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ are permutable.
An occurrence of a value $u$ of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ can be replaced by any other value $v$ such that $v$ is congruent to $u$ modulo $𝙼$ .
An occurrence of a value $u$ of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be replaced by any other value $v$ such that $v$ is congruent to $u$ modulo $𝙼$ .

Usage

A soft $𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ constraint.

Algorithm

See algorithm of the $𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚟𝚊𝚛$ constraint.

See also

hard version: $𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘$ .

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

Keywords

characteristic of a constraint: modulo.

constraint arguments: constraint between two collections of variables.

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

Arc input(s)

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

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

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

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

Graph model

Parts (A) and (B) of Figure 5.363.1 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.363.1. Initial and final graph of the $𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘_𝚟𝚊𝚛$ constraint

(a)

(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.363. soft_same_modulo_var

Figure 5.363.1. Initial and final graph of the 𝚜𝚘𝚏𝚝_𝚜𝚊𝚖𝚎_𝚖𝚘𝚍𝚞𝚕𝚘_𝚟𝚊𝚛 constraint

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