On the generalized minimum spanning tree problem
by
Martine Labbé
Université Libre de Bruxelles - Institut de Statistique et de Recherche Opérationnelle
Coauthors: Corinne Feremans (U.L.B. - I.S.R.O.), Gilbert Laporte (C.R.T. - Université de Montréal)

The Generalized Minimum Spanning Tree Problem (GMSTP) is a variant of the classical Minimum Spanning Tree Problem, in which the vertices are partitioned into clusters and the tree has to include exactly one vertex from each cluster. This problem arises in the design of the interconnection of local networks (telecommunication and transportation networks).

New integer linear formulations are presented for the problem and the relationships between the polytopes of their LP-relaxations are established.

Then the facial structure of the integer hull associated to the GMSTP is analysed and new classes of facet defining inequalities are derived. Finally, a branch-and-cut method using these inequalities is presented as well as computational experiments.

Date received: March 28, 2001