5.176. k_same_modulo

Origin

Derived from same_modulo and from k_same.

Constraint

k_same_modulo​(SETS,​M)​

Type(s)

VARIABLES

collection​(var−dvar)​

Argument(s)

SETS	collection​(set−VARIABLES)​
M	int

Restriction(s)

required​(VARIABLES,​var)​

|VARIABLES|>​0

required​(SETS,​set)​

|SETS|>​1

same_size​(SETS,​set)​

M>​0

Purpose

Given a collection of |SETS| sets, each containing the same number of domain variables, the k_same_modulo constraint enforces a same_modulo constraint between each pair of consecutive sets.

Example

( 〈 set−〈1,​9,​1,​5,​2,​1〉,​ set−〈6,​4,​1,​1,​5,​5〉,​ set−〈1,​3,​4,​2,​8,​7〉 〉,​3 )

The k_same_modulo constraint holds since:

• The first and second collections of variables are assigned 1 value in ​{0,​3,​...,​3·k}​, 3 values in ​{1,​4,​...,​1+3·k}​ and 2 values in ​{2,​5,​...,​2+3·k}​.

• The second and third collections of variables are also assigned 1 value in ​{0,​3,​...,​3·k}​, 3 values in ​{1,​4,​...,​1+3·k}​ and 2 values in ​{2,​5,​...,​2+3·k}​.

See also

same, k_same.

Key words

characteristic of a constraint: modulo.

combinatorial object: permutation.

constraint type: system of constraints, decomposition.

Arc input(s)

SETS

Arc generator

PATH↦collection​(set1,​set2)​

Arc arity

2

Arc constraint(s)

same_modulo​(set1.set,​set2.set,​M)​

Graph property(ies)

NARC=|SETS|−1

---

Graph model

Parts (A) and (B) of Figure 5.176.1 respectively show the initial and final graph associated with the Example slot. To each vertex corresponds a collection of variables, while to each arc corresponds a same_modulo constraint.

Figure 5.176.1. Initial and final graph of the k_same_modulo constraint

(a)	(b)