A comparative analysis of several formulations for the generalized minimum spanning tree problem

A comparative analysis of several formulations for the generalized minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor20031159
Country: United States
Volume: 39
Issue: 1
Start Page Number: 29
End Page Number: 34
Publication Date: Jan 2002
Journal: Networks
Authors: , ,
Keywords: programming: network
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.

Reviews

Required fields are marked *. Your email address will not be published.