Class AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraph

java.lang.Object
org.jgrapht.alg.spanning.AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraph
Enclosing class:
AhujaOrlinSharmaCapacitatedMinimumSpanningTree<V,E>

private class AhujaOrlinSharmaCapacitatedMinimumSpanningTree.ImprovementGraph extends Object
This class realises the improvement graph for the composite multi-exchange large neighborhood search. The improvement graph encodes two exchange classes: - cyclic exchange (on vertices and subtrees) - path exchange (on vertices and subtrees)

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.