Premium
A comparative analysis of several formulations for the generalized minimum spanning tree problem
Author(s) -
Feremans Corinne,
Labbé Martine,
Laporte Gilbert
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10009
Subject(s) - minimum spanning tree , polytope , spanning tree , heuristics , combinatorics , mathematics , tree (set theory) , mathematical optimization , computer science
Abstract This article describes eight formulations for the Generalized Minimum Spanning Tree Problem (GMSTP). Relationships between the polytopes of their linear relaxations are established. It is shown that four of these polytopes are strictly included in the remaining ones. This analysis suggests which formulations should be preferred for the construction of a branch‐and‐cut algorithm and for the evaluation of heuristics. © 2002 John Wiley & Sons, Inc.