The Quadratic Minimal Spanning Tree Problem And Related Topics

This dissertation investigates a new network optimization problem, obtained by defining a quadratic cost structure on trees in networks. For this reason, we refer to (?) as the Quadratic Minimal Spanning Tree Problem. Very little previous work on this problem exists in literature. In this dissertation, we prove that this problem is NP-hard hence we must use branch-and-bound algorithms to solve it to optlmalty or resort to heuristic algorithms to solve it approximately. A number of bounding techniques based on linear programming, Lagrangean relaxation, decomposition arguments, and a parametrlzatlon bounding technique are developed and compared. The parametrlzatlon bounding technique leads to an interesting optimization problem: Find the m -dimensional vector of parameters that maximizes a plecewlse linear concave function. The maximum provides a good lower bound for the Quadratic Minimal Spanning Tree Problem. A new method called the Leveling Method is proposed in lleu of the generally used (but cumbersome) subgradlent search technique. Computational experiments show that the leveling method is very efficient and reliable for solving the above parameter search problem.The leveling method is then generalized to a broader class of Quadratic 0-1 programs. Several theorems ensure its convergence to the best parameters. The method is applied to a famous combinatorial optimization problem -- the Qua-...