Enhanced second order algorithm applied to the capacitated minimum spanning tree problem

Given a centralized undirected graph with costs associated with its edges, the capacitated minimum spanning tree problem is to find a minimum cost spanning tree of the given graph, subject to a capacity constraint in all subtrees incident in the central node. As the problem is NP-hard, we propose an enhanced version of the well-known second order algorithm, described in [Karnaugh M. A new class of algorithms for multipoint network optimization. IEEE Transactions on Communications 1976;COM-24:500–5.]. The original version of this algorithm is based on a look-ahead strategy, used for a tentative inclusion of a constraint to the problem, performed in each iteration. In the new enhanced version, we propose the inclusion of look-behind steps, which can be seen as the reverse of the look-ahead procedure. Therefore and using some memory features, the method can continue even when facing the traditional stopping criterion of the original algorithm. Computational experiments showing the effectiveness of the new method on benchmark instances are reported.