Global Constraint Catalog: Cinverse_within

5.202. inverse_within_range

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚒𝚗𝚟𝚎𝚛𝚜𝚎$ .

Constraint

$𝚒𝚗𝚟𝚎𝚛𝚜𝚎_𝚠𝚒𝚝𝚑𝚒𝚗_𝚛𝚊𝚗𝚐𝚎 (𝚇, 𝚈)$

Synonyms

$𝚒𝚗𝚟𝚎𝚛𝚜𝚎_𝚒𝚗_𝚛𝚊𝚗𝚐𝚎$ , $𝚒𝚗𝚟𝚎𝚛𝚜𝚎_𝚛𝚊𝚗𝚐𝚎$ .

Arguments

$𝚇$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚈$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚇, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚈, 𝚟𝚊𝚛)

Purpose

If the $i^{t h}$ variable of the collection $𝚇$ is assigned to $j$ and if $j$ is greater than or equal to 1 and less than or equal to the number of items of the collection $𝚈$ then the $j^{t h}$ variable of the collection $𝚈$ is assigned to $i$ .

Conversely, if the $j^{t h}$ variable of the collection $𝚈$ is assigned to $i$ and if $i$ is greater than or equal to 1 and less than or equal to the number of items of the collection $𝚇$ then the $i^{t h}$ variable of the collection $𝚇$ is assigned to $j$ .

Example

(〈9, 4, 2〉, 〈9, 3, 9, 2〉)

Since the second item of $𝚇$ is assigned to 4, the fourth item of $𝚈$ is assigned to 2. Similarly, since the third item of $𝚇$ is assigned to 2, the second item of $𝚈$ is assigned to 3. Figure 5.202.1 illustrates the correspondence between $𝚇$ and $𝚈$ .

Figure 5.202.1. Correspondence between the items of $𝚇 = 〈 9, 4, 2 〉$ and the items of $𝚈 = 〈 9, 3, 9, 2 〉$ : on the $𝚇$ side values between 1 and $| 𝚈 | = 4$ are shown in blue, on the $𝚈$ side values between 1 and $| 𝚇 | = 3$ are shown in red.

Typical

| 𝚇 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚇 . 𝚟𝚊𝚛) > 1

| 𝚈 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚈 . 𝚟𝚊𝚛) > 1

Symmetry

Arguments are permutable w.r.t. permutation $(𝚇, 𝚈)$ .

Usage

Consider an integer value $m$ and a sequence of $n$ variables $S$ from which you have to select a subsequence $S^{'}$ such that:

All variables of $S^{'}$ have to be assigned to distinct values from $[1, m]$ ,
All variables not in $S^{'}$ have to be assigned a value, not necessarily distinct, outside $[1, m]$ .

As for the $𝚒𝚗𝚟𝚎𝚛𝚜𝚎$ constraint we may want to create explicitly a value variable for each value in [1,m] in order to state some specific constraints on the value variables or to use a heuristics involving the original variables of $S$ as well as the value variables. The purpose of the $𝚒𝚗𝚟𝚎𝚛𝚜𝚎_𝚠𝚒𝚝𝚑𝚒𝚗_𝚛𝚊𝚗𝚐𝚎$ constraint is to link the variables of $S$ with the value variables.

specialisation: $𝚒𝚗𝚟𝚎𝚛𝚜𝚎$ (the 2 collections have not necessarly the same number of items).

Keywords

constraint type: graph constraint.

final graph structure: bipartite, no loop, symmetric.

heuristics: heuristics.

modelling: channelling constraint, dual model.

Arc input(s)

$𝚇$ $𝚈$

Arc generator

𝑆𝑌𝑀𝑀𝐸𝑇𝑅𝐼𝐶_𝑃𝑅𝑂𝐷𝑈𝐶𝑇

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚜 1, 𝚜 2)

Arc arity

Arc constraint(s)

𝚜 1 . 𝚟𝚊𝚛 = 𝚜 2 . 𝚔𝚎𝚢

Graph class

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

•

𝚂𝚈𝙼𝙼𝙴𝚃𝚁𝙸𝙲

Global Constraint Catalog

5. Global Constraint Catalogue

5.202. inverse_within_range

Figure 5.202.1. Correspondence between the items of 𝚇=〈9,4,2〉 and the items of 𝚈=〈9,3,9,2〉: on the 𝚇 side values between 1 and |𝚈|=4 are shown in blue, on the 𝚈 side values between 1 and |𝚇|=3 are shown in red.

Figure 5.202.1. Correspondence between the items of $𝚇 = 〈 9, 4, 2 〉$ and the items of $𝚈 = 〈 9, 3, 9, 2 〉$ : on the $𝚇$ side values between 1 and $| 𝚈 | = 4$ are shown in blue, on the $𝚈$ side values between 1 and $| 𝚇 | = 3$ are shown in red.