5.91. cycle_or_accessibility

DESCRIPTIONLINKSGRAPH
Origin

Inspired by [LabbeLaporteRodriguezMartin98].

Constraint

πšŒπš’πšŒπš•πšŽ_πš˜πš›_πšŠπšŒπšŒπšŽπšœπšœπš’πš‹πš’πš•πš’πšπš’(π™Όπ™°πš‡π™³π™Έπš‚πšƒ,π™½π™²πšˆπ™²π™»π™΄,π™½π™Ύπ™³π™΄πš‚)

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

Consider a digraph G described by the π™½π™Ύπ™³π™΄πš‚ collection. Cover a subset of the vertices of G by a set of vertex-disjoint circuits in such a way that the following property holds: for each uncovered vertex v 1 of G there exists at least one covered vertex v 2 of G such that the Manhattan distance between v 1 and v 2 is less than or equal to π™Όπ™°πš‡π™³π™Έπš‚πšƒ.

Example
3,2,πš’πš—πšπšŽπš‘-1𝚜𝚞𝚌𝚌-6𝚑-4𝚒-5,πš’πš—πšπšŽπš‘-2𝚜𝚞𝚌𝚌-0𝚑-9𝚒-1,πš’πš—πšπšŽπš‘-3𝚜𝚞𝚌𝚌-0𝚑-2𝚒-4,πš’πš—πšπšŽπš‘-4𝚜𝚞𝚌𝚌-1𝚑-2𝚒-6,πš’πš—πšπšŽπš‘-5𝚜𝚞𝚌𝚌-5𝚑-7𝚒-2,πš’πš—πšπšŽπš‘-6𝚜𝚞𝚌𝚌-4𝚑-4𝚒-7,πš’πš—πšπšŽπš‘-7𝚜𝚞𝚌𝚌-0𝚑-6𝚒-4

FigureΒ 5.91.1 represents the solution associated with the example. The covered vertices are coloured in blue, while the links starting from the uncovered vertices are dashed. The πšŒπš’πšŒπš•πšŽ_πš˜πš›_πšŠπšŒπšŒπšŽπšœπšœπš’πš‹πš’πš•πš’πšπš’ constraint holds since:

  • In the solution we have π™½π™²πšˆπ™²π™»π™΄=2 disjoint circuits.

  • All the 3 uncovered nodes are located at a distance that does not exceed π™Όπ™°πš‡π™³π™Έπš‚πšƒ=3 from at least one covered node.

Figure 5.91.1. Final graph associated with the facilities location problem
ctrs/cycle_or_accessibility1
Typical
π™Όπ™°πš‡π™³π™Έπš‚πšƒ>0
π™½π™²πšˆπ™²π™»π™΄<|π™½π™Ύπ™³π™΄πš‚|
|π™½π™Ύπ™³π™΄πš‚|>2
Symmetries
  • Items of π™½π™Ύπ™³π™΄πš‚ are permutable.

  • Attributes of π™½π™Ύπ™³π™΄πš‚ are permutable w.r.t. permutation (πš’πš—πšπšŽπš‘) (𝚜𝚞𝚌𝚌) (𝚑,𝚒) (permutation applied to all items).

  • One and the same constant can be added to the 𝚑 attribute of all items of π™½π™Ύπ™³π™΄πš‚.

  • One and the same constant can be added to the 𝚒 attribute of all items of π™½π™Ύπ™³π™΄πš‚.

Remark

This kind of facilities location problem is described in Β [LabbeLaporteRodriguezMartin98] pages. In addition to our example they also mention the cost problem that is usually a trade-off between the vertices that are directly covered by circuits and the others.

See also

common keyword: πšŒπš’πšŒπš•πšŽΒ (graph constraint).

used in graph description: πš—πšŸπšŠπš•πšžπšŽπšœ_πšŽπš‘πšŒπšŽπš™πš_0.

Keywords

constraint type: graph constraint.

final graph structure: strongly connected component.

geometry: geometrical constraint.

problems: facilities location problem.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘
Graph property(ies)
β€’ 𝐍𝐓𝐑𝐄𝐄=0
β€’ 𝐍𝐂𝐂=π™½π™²πšˆπ™²π™»π™΄

Arc input(s)

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

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

Arc arity
Arc constraint(s)
β‹πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘,β‹€πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=0,πš—πš˜πšπšŽπšœ2.πšœπšžπšŒπšŒβ‰ 0,πšŠπš‹πšœ(πš—πš˜πšπšŽπšœ1.𝚑-πš—πš˜πšπšŽπšœ2.𝚑)+πšŠπš‹πšœ(πš—πš˜πšπšŽπšœ1.𝚒-πš—πš˜πšπšŽπšœ2.𝚒)β‰€π™Όπ™°πš‡π™³π™Έπš‚πšƒ
Graph property(ies)
𝐍𝐕𝐄𝐑𝐓𝐄𝐗=|π™½π™Ύπ™³π™΄πš‚|

Sets
π–―π–±π–€π–£β†¦πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ-πšŒπš˜πš•πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšŸπšŠπš›-π™½π™Ύπ™³π™΄πš‚.𝚜𝚞𝚌𝚌)],πšπšŽπšœπšπš’πš—πšŠπšπš’πš˜πš—

Constraint(s) on sets
πš—πšŸπšŠπš•πšžπšŽπšœ_πšŽπš‘πšŒπšŽπš™πš_0(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,=,1)
Graph model

For each vertex v we have introduced the following attributes:

  • πš’πš—πšπšŽπš‘: the label associated with v,

  • 𝚜𝚞𝚌𝚌: if v is not covered by a circuit then 0; If v is covered by a circuit then index of the successor of v.

  • 𝚑: the 𝚑-coordinate of v,

  • 𝚒: the 𝚒-coordinate of v.

The first graph constraint enforces all vertices, which have a non-zero successor, to form a set of π™½π™²πšˆπ™²π™»π™΄ vertex-disjoint circuits.

The final graph associated with the second graph constraint contains two types of arcs:

  • The arcs belonging to one circuit (i.e.,Β πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=πš—πš˜πšπšŽπšœ2.πš’πš—πšπšŽπš‘),

  • The arcs between one vertex v 1 that does not belong to any circuit (i.e.,Β πš—πš˜πšπšŽπšœ1.𝚜𝚞𝚌𝚌=0) and one vertex v 2 located on a circuit (i.e.,Β πš—πš˜πšπšŽπšœ2.πšœπšžπšŒπšŒβ‰ 0) such that the Manhattan distance between v 1 and v 2 is less than or equal to π™Όπ™°πš‡π™³π™Έπš‚πšƒ.

In order to specify the fact that each vertex is involved in at least one arc we use the graph property 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = |π™½π™Ύπ™³π™΄πš‚|. Finally the dynamic constraint πš—πšŸπšŠπš•πšžπšŽπšœ_πšŽπš‘πšŒπšŽπš™πš_0(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,=,1) expresses the fact that, for each vertex v, there is exactly one predecessor of v that belongs to a circuit.

PartsΒ (A) andΒ (B) of FigureΒ 5.91.2 respectively show the initial and final graph associated with the second graph constraint of the Example slot.

Figure 5.91.2. Initial and final graph of the πšŒπš’πšŒπš•πšŽ_πš˜πš›_πšŠπšŒπšŒπšŽπšœπšœπš’πš‹πš’πš•πš’πšπš’ constraint
ctrs/cycle_or_accessibilityActrs/cycle_or_accessibilityB
(a) (b)
Signature

Since |π™½π™Ύπ™³π™΄πš‚| is the maximum number of vertices of the final graph associated with the second graph constraint we can rewrite 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 = |π™½π™Ύπ™³π™΄πš‚| to 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 β‰₯ |π™½π™Ύπ™³π™΄πš‚|. This leads to simplify 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β― Μ² to 𝐍𝐕𝐄𝐑𝐓𝐄𝐗 Β―.