Using lagrangean relaxation for solving the minimum spanning tree problem with conflicts

This thesis studies minimum spanning tree problem with conflicts, which is known to be NP-hard. Given an edge weighted graph and a set of conflicting edge pairs, the goal is to find a minimum cost spanning tree which does not contain any conflicting edge pair. In this study, a Lagrangean Relaxation scheme is proposed to obtain lower bound on the optimum objective value and Lagrangean dual problem is solved via subgradient algorithm. A Lagrangean heuristic is also devised which is combined with a simple local search in order to obtain upper bounds from infeasible solutions obtained throughout the iterations of the subgradient algorithm. Extensive computational experiments show that the proposed Lagrangean relaxation scheme and the Lagrangean heuristic outperforms the ones proposed in the literature either in terms of time efficiency or bound quality. The Lagrangean relaxation scheme and the Lagrangean heuristic are then embedded in a branch-and-bound algorithm, along with a preprocessing procedure, an infeasibility test procedure and valid inequalities to create an exact solution algorithm. The exact solution algorithm proposed in this study is also compared with the ones in the literature and state of the art commercial solver Gurobi 9.5.2. Positive and negative aspects of using Lagrangean relaxation in a branch-and-bound algorithm are also discussed.