Heuristics and Meta heuristics for some Constrained Spanning Tree Generation Problems

Abstract

Given a graph G=(V,E) with associated positive, non-zero edge weights, the Minimum Spanning Tree (MST) problem finds a connected, acyclic sub-graph T of G of minimum weight. The problem is well studied and solvable to proven optimality in polynomial time, c.f. (Boruvka, 1926), (Kruskal, 1956), (Prim, 1957) and others. However, when constraints are applied, such as a bound on the degree or diameter of vertices, or the number of leaves of a spanning tree, the problem becomes much harder to solve. Constrained Spanning Tree generation problems occur widely in domains such as Information Retrieval, telecommunication network design, VLSI, facility location and transportation networks. newline This thesis presents several novel heuristics, meta-heuristics and parallel implementations for three constrained spanning tree generation problems, all of which are known to be NP-hard (Garey and Johnson, 1979). These are the Bounded-diameter Minimum Spanning Tree (BDMST) Problem, the bi-objective Minimum Diameter-Cost Spanning Tree (bi-MDCST) Problem and the Leaf Constrained Minimum Spanning Tree (LCMST) Problem. Novel fast and effective heuristics are presented for each problem, and shown to obtain solutions that are generally of superior quality vis-à-vis the best known heuristics in the literature. Some of the proposed heuristics are designed to take asymptotically lesser time than any of the extant heuristics. These heuristics are applied for solving much larger problem sizes than attempted thus far in the literature. Novel hybrid meta-heuristics are proposed that obtain better quality results and also significantly reduce the number of iterations/generations/function evaluations vis-à-vis the best known meta-heuristics in the literature. Further, parallel versions of the novel heuristics and meta-heuristics that harness the power of current multi- and many- core architectures are implemented as applicable and effective, and shown to scale well with problem size. The proposed heuristics and meta-heuristics are rigorously compared with the best known extant algorithms in the course of several computational experiments and shown to obtain superior performance over a wide range of benchmark problem instances. Results are reported for the first time in this thesis for much larger problem instances than attempted hitherto in the literature. newline newline