5.105. cycle_or_accessibility
| DESCRIPTION | LINKS | GRAPH |
- Origin
Inspired by [LabbeLaporteRodriguezMartin98].
- Constraint
- Arguments
- Restrictions
- Purpose
Consider a digraph described by the collection. Cover a subset of the vertices of by a set of vertex-disjoint circuits in such a way that the following property holds: for each uncovered vertex of there exists at least one covered vertex of such that the Manhattan distance between and is less than or equal to .
- Example
-
FigureΒ 5.105.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 disjoint circuits.
All the 3 uncovered nodes are located at a distance that does not exceed from at least one covered node.
Figure 5.105.1. Final graph associated with the facilities location problem
- Typical
- 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 .
- Arg. properties
Functional dependency: determined by .
- 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
- Keywords
constraint type: graph constraint.
final graph structure: strongly connected component.
geometry: geometrical constraint.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Sets
-
- Constraint(s) on sets
- Graph model
For each vertex we have introduced the following attributes:
: the label associated with ,
: if is not covered by a circuit then 0; If is covered by a circuit then index of the successor of .
: the -coordinate of ,
: the -coordinate of .
The first graph constraint forces 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.,Β ),
The arcs between one vertex that does not belong to any circuit (i.e.,Β ) and one vertex located on a circuit (i.e.,Β ) such that the Manhattan distance between and 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 expresses the fact that, for each vertex , there is exactly one predecessor of that belongs to a circuit.
PartsΒ (A) andΒ (B) of FigureΒ 5.105.2 respectively show the initial and final graph associated with the second graph constraint of the Example slot.
Figure 5.105.2. Initial and final graph of the constraint
(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 .