5.54. circuit_cluster

DESCRIPTIONLINKSGRAPH
Origin

Inspired by [LaporteAsefVaziriSriskandarajah96].

Constraint

πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš›(π™½π™²π™Έπšπ™²πš„π™Έπšƒ,π™½π™Ύπ™³π™΄πš‚)

Arguments
π™½π™²π™Έπšπ™²πš„π™ΈπšƒπšπšŸπšŠπš›
π™½π™Ύπ™³π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš—πšπšŽπš‘-πš’πš—πš,πšŒπš•πšžπšœπšπšŽπš›-πš’πš—πš,𝚜𝚞𝚌𝚌-πšπšŸπšŠπš›)
Restrictions
π™½π™²π™Έπšπ™²πš„π™Έπšƒβ‰₯1
π™½π™²π™Έπšπ™²πš„π™Έπšƒβ‰€|π™½π™Ύπ™³π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(π™½π™Ύπ™³π™΄πš‚,[πš’πš—πšπšŽπš‘,πšŒπš•πšžπšœπšπšŽπš›,𝚜𝚞𝚌𝚌])
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰₯1
π™½π™Ύπ™³π™΄πš‚.πš’πš—πšπšŽπš‘β‰€|π™½π™Ύπ™³π™΄πš‚|
πšπš’πšœπšπš’πš—πšŒπš(π™½π™Ύπ™³π™΄πš‚,πš’πš—πšπšŽπš‘)
π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌β‰₯1
π™½π™Ύπ™³π™΄πš‚.πšœπšžπšŒπšŒβ‰€|π™½π™Ύπ™³π™΄πš‚|
Purpose

Consider a digraph G, described by the π™½π™Ύπ™³π™΄πš‚ collection, such that its vertices are partitioned among several clusters. π™½π™²π™Έπšπ™²πš„π™Έπšƒ is the number of circuits containing more than one vertex used for covering G in such a way that each cluster is visited by exactly one circuit of length greater than 1.

Example
1,πš’πš—πšπšŽπš‘-1πšŒπš•πšžπšœπšπšŽπš›-1𝚜𝚞𝚌𝚌-1,πš’πš—πšπšŽπš‘-2πšŒπš•πšžπšœπšπšŽπš›-1𝚜𝚞𝚌𝚌-4,πš’πš—πšπšŽπš‘-3πšŒπš•πšžπšœπšπšŽπš›-2𝚜𝚞𝚌𝚌-3,πš’πš—πšπšŽπš‘-4πšŒπš•πšžπšœπšπšŽπš›-2𝚜𝚞𝚌𝚌-5,πš’πš—πšπšŽπš‘-5πšŒπš•πšžπšœπšπšŽπš›-3𝚜𝚞𝚌𝚌-8,πš’πš—πšπšŽπš‘-6πšŒπš•πšžπšœπšπšŽπš›-3𝚜𝚞𝚌𝚌-6,πš’πš—πšπšŽπš‘-7πšŒπš•πšžπšœπšπšŽπš›-3𝚜𝚞𝚌𝚌-7,πš’πš—πšπšŽπš‘-8πšŒπš•πšžπšœπšπšŽπš›-4𝚜𝚞𝚌𝚌-2,πš’πš—πšπšŽπš‘-9πšŒπš•πšžπšœπšπšŽπš›-4𝚜𝚞𝚌𝚌-9
2,πš’πš—πšπšŽπš‘-1πšŒπš•πšžπšœπšπšŽπš›-1𝚜𝚞𝚌𝚌-1,πš’πš—πšπšŽπš‘-2πšŒπš•πšžπšœπšπšŽπš›-1𝚜𝚞𝚌𝚌-4,πš’πš—πšπšŽπš‘-3πšŒπš•πšžπšœπšπšŽπš›-2𝚜𝚞𝚌𝚌-3,πš’πš—πšπšŽπš‘-4πšŒπš•πšžπšœπšπšŽπš›-2𝚜𝚞𝚌𝚌-2,πš’πš—πšπšŽπš‘-5πšŒπš•πšžπšœπšπšŽπš›-3𝚜𝚞𝚌𝚌-5,πš’πš—πšπšŽπš‘-6πšŒπš•πšžπšœπšπšŽπš›-3𝚜𝚞𝚌𝚌-9,πš’πš—πšπšŽπš‘-7πšŒπš•πšžπšœπšπšŽπš›-3𝚜𝚞𝚌𝚌-7,πš’πš—πšπšŽπš‘-8πšŒπš•πšžπšœπšπšŽπš›-4𝚜𝚞𝚌𝚌-8,πš’πš—πšπšŽπš‘-9πšŒπš•πšžπšœπšπšŽπš›-4𝚜𝚞𝚌𝚌-6
Figure 5.54.1. Four clusters and a covering with one circuit corresponding to the first example
ctrs/circuit_cluster1

Both examples involve 9 vertices 1,2,...,9 such that vertices 1 and 2 belong to cluster number 1, vertices 3 and 4 belong to cluster number 2, vertices 5, 6 and 7 belong to cluster number 3, and vertices 8 and 9 belong to cluster number 4.

The first example involves only one single circuit containing more than one vertex (i.e.,Β see in FigureΒ 5.54.1 the circuit 2β†’4β†’5β†’8β†’2). The corresponding πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš› constraint holds since exactly one vertex of each cluster (i.e.,Β vertex 2 for cluster 1, vertex 4 for cluster 2, vertex 5 for cluster 3, vertex 8 for cluster 4) belongs to this circuit.

The second example contains the two circuits 2β†’4β†’2 and 6β†’9β†’6 that both involve more than one vertex. The corresponding πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš› constraint holds since exactly one vertex of each cluster (i.e.,Β see in FigureΒ 5.54.2 vertex 2 in 2β†’4β†’2 for cluster 1, vertex 4 in 2β†’4β†’2 for cluster 2, vertex 6 in 6β†’9β†’6 for cluster 3, vertex 9 in 6β†’9β†’6 for cluster 4) belongs to these two circuits.

Figure 5.54.2. The same clusters as in the first example and a covering with two circuits corresponding to the second example
ctrs/circuit_cluster2
Typical
π™½π™²π™Έπšπ™²πš„π™Έπšƒ<|π™½π™Ύπ™³π™΄πš‚|
|π™½π™Ύπ™³π™΄πš‚|>2
πš›πšŠπš—πšπšŽ(π™½π™Ύπ™³π™΄πš‚.πšŒπš•πšžπšœπšπšŽπš›)>1
Symmetry

Items of π™½π™Ύπ™³π™΄πš‚ are permutable.

Usage

A related abstraction in Operations Research was introduced in [LaporteAsefVaziriSriskandarajah96]. It was reported as the Generalised Travelling Salesman Problem (GTSP). The πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš› constraint differs from the GTSP because of the two following points:

  • Each node of our graph belongs to one single cluster,

  • We do not constrain the number of circuits to be equal to 1: The number of circuits should be equal to one of the values of the domain of the variable π™½π™²π™Έπšπ™²πš„π™Έπšƒ.

See also

common keyword: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πšΒ (permutation), πšŒπš’πš›πšŒπšžπš’πš, πšŒπš’πšŒπš•πšŽΒ (graph constraint, one_succ).

used in graph description: πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš, πš—πšŸπšŠπš•πšžπšŽπšœ.

Keywords

combinatorial object: permutation.

constraint type: graph constraint.

final graph structure: strongly connected component, one_succ.

modelling: cluster.

Arc input(s)

π™½π™Ύπ™³π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš—πš˜πšπšŽπšœ1,πš—πš˜πšπšŽπšœ2)

Arc arity
Arc constraint(s)
β€’ πš—πš˜πšπšŽπšœ1.πšœπšžπšŒπšŒβ‰ πš—πš˜πšπšŽπšœ1.πš’πš—πšπšŽπš‘
β€’ πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘
Graph property(ies)
β€’ 𝐍𝐓𝐑𝐄𝐄=0
β€’ 𝐍𝐒𝐂𝐂=π™½π™²π™Έπšπ™²πš„π™Έπšƒ

Graph class
𝙾𝙽𝙴_πš‚πš„π™²π™²

Sets
𝖠𝖫𝖫_π–΅π–€π–±π–³π–¨π–’π–€π–²β†¦πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ-πšŒπš˜πš•πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšŸπšŠπš›-π™½π™Ύπ™³π™΄πš‚.πšŒπš•πšžπšœπšπšŽπš›)]

Constraint(s) on sets
β€’ πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)
β€’ πš—πšŸπšŠπš•πšžπšŽπšœ(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,=,πšœπš’πš£πšŽ(π™½π™Ύπ™³π™΄πš‚,πšŒπš•πšžπšœπšπšŽπš›))
Graph model

In order to express the binary constraint linking two vertices one has to make explicit the identifier of each vertex as well as the cluster to which belongs each vertex. This is why the πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš› constraint considers objects that have the following three attributes:

  • The attribute πš’πš—πšπšŽπš‘ that is the identifier of a vertex.

  • The attribute πšŒπš•πšžπšœπšπšŽπš› that is the cluster to which belongs a vertex.

  • The attribute 𝚜𝚞𝚌𝚌 that is the unique successor of a vertex.

The partitioning of the clusters by different circuits is expressed in the following way:

PartsΒ (A) andΒ (B) of FigureΒ 5.54.3 respectively show the initial and final graph associated with the second example of the Example slot. Since we use the 𝐍𝐒𝐂𝐂 graph property, we show the two strongly connected components of the final graph. They respectively correspond to the two circuits 2β†’4β†’2 and 6β†’9β†’6. Since all the vertices belongs to a circuit we have that 𝐍𝐓𝐑𝐄𝐄 = 0.

Figure 5.54.3. Initial and final graph of the πšŒπš’πš›πšŒπšžπš’πš_πšŒπš•πšžπšœπšπšŽπš› constraint
ctrs/circuit_clusterActrs/circuit_clusterB
(a) (b)