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

被引：33

作者：

Feremans, C

Labbé, M

Laporte, G

机构：

[1] Ecole Hautes Etud Commerciales, Montreal, PQ H3T 2A7, Canada

[2] Free Univ Brussels, Serv Optimisat, Inst Stat & Rech Operat, B-1050 Brussels, Belgium

来源：

NETWORKS | 2002年 / 39卷 / 01期

关键词：

spanning trees; integer linear programming; polytopes;

D O I：

10.1002/net.10009

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2002 John Wiley Sons, Inc.

引用

页码：29 / 34

页数：6

共 5 条

[1]

FAIGLE U, 2000, GEN MINIMUM SPANNING

[2]

Gale D., 1957, PACIFIC J MATH, V7, P1073, DOI [10.2140/pjm.1957.7.1073, DOI 10.2140/PJM.1957.7.1073]

[3] A CATALOG OF STEINER TREE FORMULATIONS [J].

GOEMANS, MX ;

MYUNG, YS .

NETWORKS, 1993, 23 (01) :19-28

[4]

Magnanti T.L., 1995, HDBK OPER R, V7, P503, DOI [10.1016/S0927-0507(05)80126-4, DOI 10.1016/S0927-0507(05)80126-4.URL, DOI 10.1016/S0927-0507(05)80126-4]

[5] ON THE GENERALIZED MINIMUM SPANNING TREE PROBLEM [J].

MYUNG, YS ;

LEE, CH ;

TCHA, DW .

NETWORKS, 1995, 26 (04) :231-241

← 1 →