Capacitated minimum spanning tree

Short description: Spanning tree type

Capacitated minimum spanning tree is a minimal cost spanning tree of a graph that has a designated root node [math]\displaystyle{ r }[/math] and satisfies the capacity constraint [math]\displaystyle{ c }[/math]. The capacity constraint ensures that all subtrees (maximal subgraphs connected to the root by a single edge) incident on the root node [math]\displaystyle{ r }[/math] have no more than [math]\displaystyle{ c }[/math] nodes. If the tree nodes have weights, then the capacity constraint may be interpreted as follows: the sum of weights in any subtree should be no greater than [math]\displaystyle{ c }[/math]. The edges connecting the subgraphs to the root node are called gates. Finding the optimal solution is NP-hard.

Algorithms

Suppose we have a graph [math]\displaystyle{ G = (V, E) }[/math], [math]\displaystyle{ n = |G| }[/math] with a root [math]\displaystyle{ r \in G }[/math]. Let [math]\displaystyle{ a_{i} }[/math] be all other nodes in [math]\displaystyle{ G }[/math]. Let [math]\displaystyle{ c_{ij} }[/math] be the edge cost between vertices [math]\displaystyle{ a_{i} }[/math] and [math]\displaystyle{ a_{j} }[/math] which form a cost matrix [math]\displaystyle{ C = {c_{ij}} }[/math].

Esau-Williams heuristic

Esau-Williams heuristic finds suboptimal CMST that are very close to the exact solutions, but on average EW produces better results than many other heuristics.

Initially, all nodes are connected to the root [math]\displaystyle{ r }[/math] (star graph) and the network's cost is [math]\displaystyle{ \displaystyle\sum_{i=0}^n c_{ri} }[/math]; each of these edges is a gate. At each iteration, we seek the closest neighbor [math]\displaystyle{ a_{j} }[/math] for every node in [math]\displaystyle{ G-{r} }[/math] and evaluate the tradeoff function: [math]\displaystyle{ t(a_{i}) = g_{i} - c_{ij} }[/math]. We look for the greatest [math]\displaystyle{ t(a_{i}) }[/math] among the positive tradeoffs and, if the resulting subtree does not violate the capacity constraints, remove the gate [math]\displaystyle{ g_{i} }[/math] connecting the [math]\displaystyle{ i }[/math]-th subtree to [math]\displaystyle{ a_{j} }[/math] by an edge [math]\displaystyle{ c_{ij} }[/math]. We repeat the iterations until we can not make any further improvements to the tree.

Esau-Williams heuristics for computing a suboptimal CMST:

function CMST(c,C,r):
    T = {[math]\displaystyle{ c_{1r} }[/math], [math]\displaystyle{ c_{2r} }[/math], ..., [math]\displaystyle{ c_{nr} }[/math]}
    while have changes:
        for each node [math]\displaystyle{ a_{i} }[/math]
            [math]\displaystyle{ a_{j} }[/math] = closest node in a different subtree
            [math]\displaystyle{ t(a_{i}) }[/math] = [math]\displaystyle{ g_{i} }[/math] - [math]\displaystyle{ c_{ij} }[/math]
        t_max = max([math]\displaystyle{ t(a_{i}) }[/math])
        k = i such that [math]\displaystyle{ t(a_{i}) }[/math] = t_max
        if ( cost(i) + cost(j) <= c)
            T = T - [math]\displaystyle{ g_{k} }[/math]
            T = T union [math]\displaystyle{ c_{kj} }[/math]
    return T

It is easy to see that EW finds a solution in polynomial time.

Sharma's heuristic

Sharma's heuristic.

Ahuja's heuristic

Ahuja's heuristic uses a local search in a large multi-exchange neighborhood from a randomized greedy initial solution.

Initial solution

The initial solution is found by using a randomized version of Esau-Williams. Randomization is achieved by executing a uniformly random join from the best [math]\displaystyle{ p }[/math] ones instead of the best one in each step.

Local Search Neighborhood

Let [math]\displaystyle{ T }[/math] be the initial solution with root [math]\displaystyle{ r }[/math]. The neighborhood consists of any combination of a single node or subtree (general subtrees, not as in the introduction of this article) displacing one in a different component of [math]\displaystyle{ T\setminus r }[/math] such that the displaced structure is the next displacer, the last displacer displaces the first displacer, no original component has more than one displacer and the capacity is not exceeded in any resulting component.

Improvement Graph

An improvement graph is a tool to search a very large neighborhood efficiently. Paths through an improvement graph correspond to changes to a solution and the cost of the path is the change in the cost of the solution when applying the change. Here the improvement graph is a directed multigraph built by using 2 copies [math]\displaystyle{ i',i'' }[/math] of each node [math]\displaystyle{ i\in V(T) }[/math] and up to 4 edges from any node to any node in a different component of [math]\displaystyle{ T\setminus r }[/math]. The edge [math]\displaystyle{ i',j'' }[/math] corresponds to the change of removing the node [math]\displaystyle{ i }[/math] from its original component and replacing the subtree rooted at [math]\displaystyle{ j }[/math] in the target component. Combining nodes [math]\displaystyle{ i' }[/math] and subtrees [math]\displaystyle{ i'' }[/math] yields the 4 possible edges. An edge exists if the corresponding change does not lead to the target component exceeding the capacity. The cost of an edge is the difference in the cost of the minimal spanning trees on the vertices in the target component before and after the displacement. Thus neighbors in the local search correspond to cycles in the improvement graph that contain at most one node from each component.

Local Search Step

The local search step uses a dynamic programming approach to find a minimum cost cycle in the improvement graph. Paths through the improvement graph with increasing length are generated and only the most favorable with the same start and end as well as involved components is stored. To this end a hash table with the tuple of those 3 properties as key is used to hold paths. Since in each negative cycle there is a node such that all paths within that cycle containing this node have negative cost, only paths with negative cost need to be considered at all. As the comparison of sets of involved components between paths is one of the most common operations in the algorithm, it is implemented as comparison of indicator bit arrays stored as integers for speed. This however clearly stems from a lot of hash collisions, which might be a consequence of the particular choice of hash function and table structure, as well as high load factor due to space restrictions (paper from 2003).

Performance

At the time the paper was written (2003) this algorithm was state of the art on a standard operations research benchmark. The execution was dominated by the building (respectively updating) of the improvement graph. The number of edges in the improvement graph empirically scaled quadratically with the size of the input graph and since this determines the number of times the comparatively complex step of finding a minimum spanning tree has to be run, this is the most critical factor. Thus one can conclude that less dense input graphs greatly benefit the running time, as this reduces the number of edges in the improvement graph.

Applications

CMST problem is important in network design: when many terminal computers have to be connected to the central hub, the star configuration is usually not the minimum cost design. Finding a CMST that organizes the terminals into subnetworks can lower the cost of implementing a network.