5.278. same

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

N.Β Beldiceanu

Constraint

πšœπšŠπš–πšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2)

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1,πšŸπšŠπš›)
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2,πšŸπšŠπš›)
Purpose

The variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 collection correspond to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 collection according to a permutation.

Example
πšŸπšŠπš›-1,πšŸπšŠπš›-9,πšŸπšŠπš›-1,πšŸπšŠπš›-5,πšŸπšŠπš›-2,πšŸπšŠπš›-1,πšŸπšŠπš›-9,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-2,πšŸπšŠπš›-5

The πšœπšŠπš–πšŽ constraint holds since values 1, 2, 5 and 9 have the same number of occurrences within both collections 〈1,9,1,5,2,1βŒͺ and 〈9,1,1,1,2,5βŒͺ. FigureΒ 5.278.1 illustrates this correspondence.

Figure 5.278.1. Correspondence between collection 〈1,9,1,5,2,1βŒͺ and collection 〈9,1,1,1,2,5βŒͺ
ctrs/same1
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

The πšœπšŠπš–πšŽ constraint can be used in the following contexts:

  • Pairing problems taken fromΒ [BeldiceanuKatrielThiel04b]. The organisation Doctors Without Borders has a list of doctors and a list of nurses, each of whom volunteered to go on one mission in the next year. Each volunteer specifies a list of possible dates and each mission involves one doctor and one nurse. The task is to produce a list of pairs such that each pair includes a doctor and a nurse who are available at the same date and each volunteer appears in exactly one pair. The problem is modelled by a πšœπšŠπš–πšŽ(D=d 1 ,d 2 ,...,d m ,N=n 1 ,n 2 ,...,n m ) constraint where each doctor is represented by a domain variable in D and each nurse by a domain variable in N. For a given doctor or nurse the corresponding domain variable gives the dates when the person is available. When the number of nurses is different from the number of doctors we replace the πšœπšŠπš–πšŽ constraint by a 𝚞𝚜𝚎𝚍_πš‹πš’ constraint.

  • Timetabling problems where we wish to produce fair schedules for different persons is a second use of the πšœπšŠπš–πšŽ constraint. Assume we need to generate a plan over a period of D consecutive days for P persons. For each day d and each person p we need to decide whether person p works in the morning shift, in the afternoon shift, in the night shift or does not work at all on day d. In a fair schedule, the number of morning shifts should be the same for all the persons. The same condition holds for the afternoon and the night shifts as well as for the days off. We create for each person p the sequence of variables v p,1 ,v p,2 ,...,v p,D . v p,D is equal to one of 0,1,2 and 3, depending on whether person p does not work, works in the morning, in the afternoon or during the night on day d. We can use P-1 πšœπšŠπš–πšŽ constraints to express the fact that v 1,1 ,v 1,2 ,...,v 1,D should be a permutation of v p,1 ,v p,2 ,...,v p,D for each (1<p≀P).

  • The πšœπšŠπš–πšŽ constraint can also be used as a channelling constraint for modelling the following recurring pattern: given the number of 1s in each line and each column of a 0-1 matrix β„³ with n rows and m columns, reconstruct the matrix. This pattern usually occurs with additional constraints about compatible positions of the 1s, or about the overall shape reconstructed from all the 1's (e.g.,Β convexity, connectivity). If we restrict ourselves to the basic pattern there is an O(mn) algorithm for reconstructing a mΒ·n matrix from its horizontal and vertical directionsΒ [Gale57]. We show how to model this pattern with the πšœπšŠπš–πšŽ constraint. Let l i (1≀i≀n) and c j (1≀j≀m) denote respectively, the required number of 1s in the ith row and the jth column of β„³. We number the entries of the matrix as shown in the left-hand side ofΒ 5.278.2. For row i we create l i domain variables v ik where k∈[1,l i ]. Similarly, for each column j we create c j domain variables u jk where k∈[1,c i ]. The domain of each variable contains the set of entries that belong to the row or column that the variable corresponds to. Thus, each domain variable represents a 1 that appears in the designated row or column. Let 𝒱 be the set of variables corresponding to rows and 𝒰 be the set of variables corresponding to columns. To make sure that each 1 is placed in a different entry, we impose the constraint πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(𝒰). In addition, the constraint πšœπšŠπš–πšŽ(𝒰,𝒱) enforces that the 1s exactly coincide on the rows and the columns. A solution is shown on the right-hand side ofΒ 5.278.2. Note that the πšœπšŠπš–πšŽ_πšŠπš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraint allows to model the matrix reconstruction problem without the additional πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint.

Figure 5.278.2. Modelling the 0-1 matrix reconstruction problem with the πšœπšŠπš–πšŽ constraint
ctrs/same3
Remark

The πšœπšŠπš–πšŽ constraint is a relaxed version of the πšœπš˜πš›πš constraint introduced inΒ [OlderSwinkelsEmden95]. We do not enforce the second collection of variables to be sorted in increasing order.

If we interpret the collections πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 as two multisets variablesΒ [KiziltanWalsh02], the πšœπšŠπš–πšŽ constraint can be considered as an equality constraint between two multisets variables.

The πšœπšŠπš–πšŽ constraint can be modelled by two πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraints. For instance, the πšœπšŠπš–πšŽ constraint

πšœπšŠπš–πšŽπšŸπšŠπš›-x 1 ,πšŸπšŠπš›-x 2 ,πšŸπšŠπš›-y 1 ,πšŸπšŠπš›-y 2 ,

where the union of the domains of the different variables is {1,2,3,4} corresponds to the conjunction of the following two πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraints:

πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’πšŸπšŠπš›-x 1 ,πšŸπšŠπš›-x 2 ,πšŸπšŠπš•-1πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-c 1 ,πšŸπšŠπš•-2πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-c 2 ,πšŸπšŠπš•-3πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-c 3 ,πšŸπšŠπš•-4πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-c 4
πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’πšŸπšŠπš›-y 1 ,πšŸπšŠπš›-y 2 ,πšŸπšŠπš•-1πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-c 1 ,πšŸπšŠπš•-2πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-c 2 ,πšŸπšŠπš•-3πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-c 3 ,πšŸπšŠπš•-4πš—πš˜πšŒπšŒπšžπš›πš›πšŽπš—πšŒπšŽ-c 4

As shown by the next example, the consistency for all variables of the two πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraints does not implies consistency for the corresponding πšœπšŠπš–πšŽ constraint. This is for instance the case when the domains of x 1 , x 2 , y 1 and y 2 is respectively equal to {1,2}, {3,4}, {1,2,3,4} and {3,4}. The conjunction of the two πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’ constraints does not remove values 3 and 4 from y 1 .

In his PhD thesis, W.-J.Β vanΒ Hoeve introduces a soft version of the πšœπšŠπš–πšŽ constraint where the cost is the minimum number of variables to unassign in order to get back to a solutionΒ [vanHoeve05]. In the context of the πšœπšŠπš–πšŽ constraint this violation cost corresponds to the difference between the number of variables in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and the number of values that both occur in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and in πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 (provided that one value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 matches at most one value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2).

Algorithm

InΒ [BeldiceanuKatrielThiel04a], [BeldiceanuKatrielThiel04b], [BeldiceanuKatrielThiel05], [Katriel05], it is shown how to model this constraint by a flow network that enables to compute arc-consistency and bound-consistency. Unlike the networks used for πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš and πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’, the network now has three sets of nodes, so the algorithms are more complex, in particular the efficient bound-consistency algorithm.

Used in

πš”_πšœπšŠπš–πšŽ.

See also

generalisation: πšŒπš˜πš›πš›πšŽπšœπš™πš˜πš—πšπšŽπš—πšŒπšŽΒ (π™Ώπ™΄πšπ™Όπš„πšƒπ™°πšƒπ™Έπ™Ύπ™½ parameter added), πšœπšŠπš–πšŽ_πš’πš—πšπšŽπš›πšŸπšŠπš•Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ/πšŒπš˜πš—πšœπšπšŠπš—πš), πšœπšŠπš–πšŽ_πš–πš˜πšπšžπš•πš˜Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ mod πšŒπš˜πš—πšœπšπšŠπš—πš), πšœπšŠπš–πšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš™πšŠπš›πšπš’πšπš’πš˜πš—).

implied by: πš•πšŽπš‘_πšŽπššπšžπšŠπš•, πšœπšŠπš–πšŽ_πšŠπš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’, πšœπšŠπš–πšŽ_πšŠπš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™, πšœπš˜πš›πš.

implies: πšœπšŠπš–πšŽ_πš’πš—πšπšŽπš›πšœπšŽπšŒπšπš’πš˜πš—, 𝚞𝚜𝚎𝚍_πš‹πš’.

related to a common problem: πšŒπš˜πš•πš˜πš›πšŽπš_πš–πšŠπšπš›πš’πš‘Β (matrix reconstruction problem).

soft variant: 𝚜𝚘𝚏𝚝_πšœπšŠπš–πšŽ_πšŸπšŠπš›Β (variable-based violation measure).

system of constraints: πš”_πšœπšŠπš–πšŽ.

Keywords

characteristic of a constraint: automaton, automaton with array of counters.

combinatorial object: permutation, multiset.

constraint arguments: constraint between two collections of variables.

filtering: flow, arc-consistency, bound-consistency, DFS-bottleneck.

modelling: channelling constraint, equality between multisets.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
β€’ for all connected components: ππ’πŽπ”π‘π‚π„=ππ’πˆππŠ
β€’ ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|
β€’ ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.278.3 respectively show the initial and final graph associated with the Example slot. Since we use the ππ’πŽπ”π‘π‚π„ and ππ’πˆππŠ graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. Each of them corresponds to an equivalence class according to the arc constraint. The πšœπšŠπš–πšŽ constraint holds since:

  • Each connected component of the final graph has the same number of sources and of sinks.

  • The number of sources of the final graph is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1|.

  • The number of sinks of the final graph is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|.

Figure 5.278.3. Initial and final graph of the πšœπšŠπš–πšŽ constraint
ctrs/sameA
(a)
ctrs/sameB
(b)
Signature

Since the initial graph contains only sources and sinks, and since isolated vertices are eliminated from the final graph, we make the following observations:

  • Sources of the initial graph cannot become sinks of the final graph,

  • Sinks of the initial graph cannot become sources of the final graph.

From the previous observations and since we use the π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡ arc generator on the collections πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2, we have that the maximum number of sources and sinks of the final graph is respectively equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| and |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2|. Therefore we can rewrite ππ’πŽπ”π‘π‚π„=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| to ππ’πŽπ”π‘π‚π„β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| and simplify ππ’πŽπ”π‘π‚π„ Β― Μ² to ππ’πŽπ”π‘π‚π„ Β―. In a similar way, we can rewrite ππ’πˆππŠ=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| to ππ’πˆππŠβ‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2| and simplify ππ’πˆππŠ Β― Μ² to ππ’πˆππŠ Β―.

Automaton

To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1 corresponds a signature variable πš‚ i that is equal to 0. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚2 corresponds a signature variable πš‚ i+|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚1| that is equal to 1.

Figure 5.278.4. Automaton of the πšœπšŠπš–πšŽ constraint
ctrs/same2