Class AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraph
- Enclosing class:
AhujaOrlinSharmaCapacitatedMinimumSpanningTree<V,
E>
DEFINITION EXCHANGES Let T[i] be the subtree rooted at i of the MST implicitly defined by the vertex partition. Cyclic Exchange: A cyclic exchange is defined on vertices i_1, ..., i_r, i_1, where the vertices represent either itself in the base graph or the subtrees rooted at i_k for k = 1, ..., r, where T[i_a] != T[i_b] for a != b. The cyclic exchange on i_1, ..., i_r, i_1 moves the i_a (or T[i_a]) to the subset of i_b, where b = a+1 mod r+1. Such a cyclic exchange is feasible if the capacity constraint is not violated. We can represent the cost of the cyclic exchange by the following formulas: Let S[i_k] be the subset of i_k in the implicitly defined partition. - exchange of vertices: $$ c(T_new) - c(T) = \sum_{a = 1}^{r} c(\{i_{a - 1}\} \cup S[i_{i_a}] \setminus \{i_a\}] $$ - exchange of rooted subtrees: $$ c(T_new) - c(T) = \sum_{a = 1}^{r} c(T[i_{a - 1}] \cup S[i_{i_a}] \setminus T[i_a]] $$ where c is the given edge cost function and T_new is the CMST resulting by executing the cyclic exchange. Thus, an exchange is profitable if c(T_new) - c(T) invalid input: '<' 0.
Path Exchange: A path exchange follows the same idea as the cyclic exchange but it does not end at the same vertex. That is, the path exchange is defined on i_1, ..., i_r. The cost function has to be adapted at the start and end point of the path.
DEFINITION NEIGHBORHOOD Furthermore, we have to define the neighborhood. These are all capacitated spanning trees that are reachable by using such an exchange as given above.
DEFINITION IMPROVEMENT GRAPH The improvement graph is based on a feasible capacitated spanning tree and uses a one-to-one correspondence between the vertices in the base graph and the vertices in the improvement graph. We want to define the arc set of the improvement graph such that each subset disjoint directed cycle (see construction) correspond to a cyclic exchange (or a path exchange, we come to that later). Furthermore, the cost of the cycle in the improvement graph and the cost of the corresponding cyclic exchange has to be equal.
CONSTRUCTION OF THE IMPROVEMENT GRAPH The improvement graph IG = (V, A) has the vertex set V, which is equal to the vertex set of the base graph. The arc set A is defined in the following: A directed arc (i, j) in IG represents that we move the node i (or the subtree T[i]) to the subset in which vertex j is. That is, vertex i and j are removed from their subset and i (or the subtree T[i]) is moved to the subset of j. This arc only exists if the exchange is feasible. Then, the cost can be defined as $$ c(\{T[i]\} \cup S[j] \setminus \{T[j]\}) - c(S[j]). $$ A directed cycle i_1, ..., i_r, i_1 in this graph subset disjoint if the subsets of the nodes are pairwise disjoint. By this definition, there is a one-to-one cost-preserving correspondence between the cyclic exchanges and the subset disjoint directed cycles in the improvement graph IG.
Identifying path exchanges: For the conversion of path exchanges into subset disjoint cycles, we have to introduce two more node types in the improvement graph: pseudo nodes and a origin node. On the one hand, pseudo nodes represent a subset of the implicitly defined partition and mark the end of the end of a path exchange. On the other hand, the origin node marks a beginning of a path exchange. Therefore, the pseudo node are connected to the origin node to induce subset disjoint cycles. The costs of the arcs from and to the pseudo nodes and the origin nodes are defined as follows: We denoted the original nodes in the improvement graph as regular nodes - c(p, o) = 0 for all pseudo nodes p and origin node o - c(o, r) = c(S[j] \setminus \{T[j]\}) - c(S[j]) for origin node o and for all regular nodes r - c(r, p) = c(\{T[i]\} \cup S[j]) - c(S[j]) for all regular nodes r and for all pseudo nodes p Again, those arc exists only if the exchange is feasible.
IDENTIFYING SUBSET DISJOINT CYCLES This is done via a heuristic which can be found here
AhujaOrlinSharmaCyclicExchangeLocalAugmentation
@see
AhujaOrlinSharmaCyclicExchangeLocalAugmentation.
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) AbstractCapacitatedMinimumSpanningTree<V,
E>.CapacitatedSpanningTreeSolutionRepresentation the current solution corresponding to the improvement graph(package private) Map
<Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, Integer> mapping form all improvement graph vertices to their labels corresponding to the base graph for the CMST problem(package private) Graph
<Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, DefaultWeightedEdge> the improvement graph itselfmapping from the vertex index in the improvement graph to the vertex in the base graphmapping from the base graph vertex to the vertex index in the improvement graph(package private) Pair
<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> the origin vertex(package private) final Integer
dummy label of the origin vertex(package private) Map
<Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, Integer> mapping from the pseudo vertices to the label of the subset they are representing(package private) Map
<Integer, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>> mapping from the label of the subsets to the corresponding vertex mapping -
Constructor Summary
ConstructorsConstructorDescriptionImprovementGraph
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation capacitatedSpanningTreeSolutionRepresentation) Constructs an new improvement graph object for this CMST algorithm instance. -
Method Summary
Modifier and TypeMethodDescriptiondouble
calculateMaximumDemandOfSubtrees
(Set<V> vertexSubset, SpanningTreeAlgorithm.SpanningTree<E> spanningTree, double totalDemand) Calculates the maximum demand over all new subtrees induced by the minimum spanning treespanningTree
.Graph
<Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, DefaultWeightedEdge> Initializes the improvement graph, i.e.private Map
<Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, Integer> Returns the mapping that is used in the valid cycle detection algorithm, i.e.void
updateImprovementGraph
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTrees, Set<Integer> labelsToUpdate, Set<V> tabuList) Updates the improvement graph.void
updateImprovementGraphEdge
(Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> v2, double newCapacity, double newCost) Adds an edge betweenv1
andv2
to the improvement graph ifnewCapacity
does not exceed the capacity constraint.private void
updateOriginNodeConnections
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTrees, Set<Integer> labelsToUpdate, V v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Single, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Subtree) Updates the edges to the origin vertex.private void
updatePseudoNodesOfNewLabels
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution) Updates the pseudo nodes corresponding to new subsets in the partition.private void
updateSingleNode
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Set<V> tabuList, int label, double oldWeight, Set<V> modifiableSet, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> pseudoVertex, V v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Single) Updates all edges fromvertexOfV1Single
to nodes in the subset represented bylabel
.private void
updateSubtreeNode
(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Set<V> tabuList, int label, double oldWeight, Set<V> modifiableSet, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> pseudoVertex, V v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Subtree) Updates all edges fromvertexOfV1Single
to nodes in the subset represented bylabel
.private boolean
updateTabuVertices
(Set<V> tabuList, V v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Single, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Subtree) Updates all nodes that correspond tov1
and returns if the vertexv1
.
-
Field Details
-
improvementGraph
Graph<Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, improvementGraphDefaultWeightedEdge> the improvement graph itself -
capacitatedSpanningTreeSolutionRepresentation
AbstractCapacitatedMinimumSpanningTree<V,E>.CapacitatedSpanningTreeSolutionRepresentation capacitatedSpanningTreeSolutionRepresentationthe current solution corresponding to the improvement graph -
cycleAugmentationLabels
Map<Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, cycleAugmentationLabelsInteger> mapping form all improvement graph vertices to their labels corresponding to the base graph for the CMST problem -
improvementGraphVertexMapping
mapping from the vertex index in the improvement graph to the vertex in the base graph -
initialVertexMapping
mapping from the base graph vertex to the vertex index in the improvement graph -
pseudoVertexMapping
Map<Integer,Pair<Integer, pseudoVertexMappingAhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>> mapping from the label of the subsets to the corresponding vertex mapping -
pathExchangeVertexMapping
Map<Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, pathExchangeVertexMappingInteger> mapping from the pseudo vertices to the label of the subset they are representing -
origin
the origin vertex -
originVertexLabel
dummy label of the origin vertex
-
-
Constructor Details
-
ImprovementGraph
public ImprovementGraph(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation capacitatedSpanningTreeSolutionRepresentation) Constructs an new improvement graph object for this CMST algorithm instance.
-
-
Method Details
-
createImprovementGraph
public Graph<Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, createImprovementGraph()DefaultWeightedEdge> Initializes the improvement graph, i.e. adds single, subtree and pseudo vertices as well as the origin vertex. Furthermore, it initializes all mappings.- Returns:
- the improvement graph itself.
-
updateImprovementGraph
public void updateImprovementGraph(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTrees, Set<Integer> labelsToUpdate, Set<V> tabuList) Updates the improvement graph. It updates the vertices and edges in the parts specified inlabelsToUpdate
.- Parameters:
currentSolution
- the current solutionsubtrees
- the mapping from vertices to their subtreepartitionSpanningTrees
- the mapping from labels of subsets to their spanning treelabelsToUpdate
- the labels of all subsets that has to be updated (because of the multi-exchange operation)
-
updatePseudoNodesOfNewLabels
private void updatePseudoNodesOfNewLabels(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution) Updates the pseudo nodes corresponding to new subsets in the partition. That is, new pseudo nodes for new labels in the label set are added and pseudo nodes of labels that are no more in the label set are removed.- Parameters:
currentSolution
- the current solution in the iteration
-
updateTabuVertices
private boolean updateTabuVertices(Set<V> tabuList, V v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Single, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Subtree) Updates all nodes that correspond tov1
and returns if the vertexv1
. That is, all incident edges ofv1
are removed ifv1
is in the tabu list.- Parameters:
tabuList
- the tabu list of the current iterationv1
- the vertex to update the nodes in the improvement graph forvertexOfV1Single
- the node in the improvement graph representing the exchange of the vertexv1
vertexOfV1Subtree
- the node in the improvement graph representing the exchange of the subtree rooted atv1
- Returns:
- true iff
v1
is in the tabu list
-
updateOriginNodeConnections
private void updateOriginNodeConnections(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Map<Integer, SpanningTreeAlgorithm.SpanningTree<E>> partitionSpanningTrees, Set<Integer> labelsToUpdate, V v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Single, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Subtree) Updates the edges to the origin vertex.- Parameters:
currentSolution
- the current solution in the iterationsubtrees
- the mapping from vertices to their subtreepartitionSpanningTrees
- the mapping from labels of subsets to their spanning treelabelsToUpdate
- the labels of all subsets that has to be updated (because of the multi-exchange operation)v1
- the vertex to update the nodes in the improvement graph forvertexOfV1Single
- the node in the improvement graph representing the exchange of the vertexv1
vertexOfV1Subtree
- the node in the improvement graph representing the exchange of the subtree rooted atv1
-
updateSingleNode
private void updateSingleNode(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Set<V> tabuList, int label, double oldWeight, Set<V> modifiableSet, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> pseudoVertex, V v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Single) Updates all edges fromvertexOfV1Single
to nodes in the subset represented bylabel
.- Parameters:
currentSolution
- the current solution in the iterationsubtrees
- the mapping from vertices to their subtreetabuList
- the tabu list of the current iterationlabel
- the current label to update the edges foroldWeight
- the old weight of the subsetmodifiableSet
- a modifiable version of the subset of nodes represented by label inclusive the root nodepseudoVertex
- the pseudo vertex representing the subset represented by labelv1
- the vertex to update the nodes in the improvement graph forvertexOfV1Single
- the node in the improvement graph representing the exchange of the vertexv1
-
updateSubtreeNode
private void updateSubtreeNode(AbstractCapacitatedMinimumSpanningTree<V, E>.CapacitatedSpanningTreeSolutionRepresentation currentSolution, Map<V, Pair<Set<V>, Double>> subtrees, Set<V> tabuList, int label, double oldWeight, Set<V> modifiableSet, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> pseudoVertex, V v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> vertexOfV1Subtree) Updates all edges fromvertexOfV1Single
to nodes in the subset represented bylabel
. This method does adds the subtree of v1 tomodifiableSet
.- Parameters:
currentSolution
- the current solution in the iterationsubtrees
- the mapping from vertices to their subtreetabuList
- the tabu list of the current iterationlabel
- the current label to update the edges foroldWeight
- the old weight of the subsetmodifiableSet
- a modifiable version of the subset of nodes represented by labelpseudoVertex
- the pseudo vertex representing the subset represented by labelv1
- the vertex to update the nodes in the improvement graph forvertexOfV1Subtree
- the node in the improvement graph representing the exchange of the subtree rooted atv1
-
updateImprovementGraphEdge
public void updateImprovementGraphEdge(Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> v1, Pair<Integer, AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType> v2, double newCapacity, double newCost) Adds an edge betweenv1
andv2
to the improvement graph ifnewCapacity
does not exceed the capacity constraint. The weight of the edge isnewCost
.- Parameters:
v1
- start vertex (the vertex or subtree induced byv1
that will be moved to the subset ofv2
)v2
- end vertex (the vertex or subtree induced byv2
that will be removed from the subset ofv2
)newCapacity
- the used capacity by adding the vertex or subtree induced byv1
to the subset ofv2
and deleting the vertex or subtree induced byv2
newCost
- the cost of the edge (the cost induced by the operation induced byv1
andv2
)
-
calculateMaximumDemandOfSubtrees
public double calculateMaximumDemandOfSubtrees(Set<V> vertexSubset, SpanningTreeAlgorithm.SpanningTree<E> spanningTree, double totalDemand) Calculates the maximum demand over all new subtrees induced by the minimum spanning treespanningTree
. A spanning tree induces more than one subset in the partition if the root vertex of the base graph connects more than one subtree of the spanning tree.- Parameters:
vertexSubset
- the vertex subsetspanning Tree is defined on
spanningTree
- the spanning treetotalDemand
- the total demand of the whole spanning tree- Returns:
- the maximum demand over all new subtrees induced by the minimum spanning tree
spanningTree
-
getImprovementGraphLabelMap
private Map<Pair<Integer,AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraphVertexType>, getImprovementGraphLabelMap()Integer> Returns the mapping that is used in the valid cycle detection algorithm, i.e. the vertex label map.- Returns:
- the vertex label map used in the valid cycle detection algorithm
-