Several variants of Generalized Minimum Spanning Tree Problems (GMSTPs) have been introduced in the literature in different papers by a number of authors. Roughly speaking, all these variants are generalizations of the classical Minimum Spanning Tree on an undirected graph G=(V,E) in which the node set V is partitioned into a given set of clusters, and the minimum tree has to ``span'' those clusters instead of simple nodes.
In particular, in this paper we are concerned with two specific variants, the most classical one in which Exactly one node in each cluster has to be visited (E-GMSTP), and the less studied problem in which at Least one node in each cluster has to be reached (L-GMSTP).
This paper presents several effective techniques to improve on the branch-and-cut approaches for E-GMSTP and L-GMSTP proposed by Feremans, Labbe and Laporte [8] and by Feremans [6], respectively. In particular, we improved on the performances through: i ) new effective heuristic algorithms, ii ) updated branching strategies, and iii ) the use of general-purpose Chvatal-Gomory cuts.
Finally, a generalization of both problems requiring some clusters to be visited exactly once and the remaining clusters at least once is presented.
|
|
|
