A feasibility pump and a local branching heuristics for the weight-constrained minimum spanning tree problem

Abstract

The Weight-constrained Minimum Spanning Tree problem (WMST) is a combinatorial optimization problem aiming to find a spanning tree of minimum cost with total edge weight not exceeding a given specified limit. This problem has important applications in the telecommunications network design and communication networks.

In order to obtain optimal or near optimal solutions to the WMST problem we use heuristic methods based on formulations for finding feasible solutions. The feasibility pump heuristic starts with the LP solution, iteratively fixes the values of some variables and solves the corresponding LP problem until a feasible solution is achieved. In the local branching heuristic a feasible solution is improved by using a local search scheme in which the solution space is reduced to the neighborhood of a feasible solution that is explored for a better feasible solution. Extensive computational results show that these heuristics are quite effective in finding feasible solutions and present small gap values. Each heuristic can be used independently, however the best results were obtained when they are used together and the feasible solution obtained by the feasibility pump heuristic is improved by the local branching heuristic.