We consider the minimum weighted k-cardinality tree problem, i.e. the problem of finding in a given undirected weighted graph G a subtree with k edges, having a minimum weight. Applications of this problem arise in oil-field leasing and facility layout. This problem differs from the classical Steiner problem in that we have no required nodes, and can be formulated as an integer programming problem. It is, however, notoriously difficult to solve for large scale problems, even when modern methods based on polyhedral combinatorics and branch and cut ideas are being used. In this paper we will present a Tabu Search heuristic approach to the solution of the minimum weighted k-cardinality tree problem. Our heuristic search method uses a neighborhood defined by edge swapping, and we develop a candidate list strategy combining greedy and diversifying aspects to overcome the prohibitively large neighbourhood size. We also report on the effect of using more than one tabu list as well as on basic Tabu Search diversification and intensification schemes.
