Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem

被引：15

作者：

Leitner, Markus ^{[1
,2
]}

机构：

[1] Univ Vienna, Dept Stat & Operat Res, A-1010 Vienna, Austria

[2] Univ Libre Bruxelles, Dept Comp Sci, B-1050 Brussels, Belgium

来源：

COMPUTERS & OPERATIONS RESEARCH | 2016年 / 65卷

基金：

奥地利科学基金会;

关键词：

Integer programming; Branch-and-cut; Generalized network design; Hop-constraints; Layered graph; SEARCH; NETWORKS; DESIGN;

D O I：

10.1016/j.cor.2015.06.012

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper studies the generalized hop-constrained minimum spanning tree problem (GHMSTP) which has applications in backbone network design subject to quality-of-service constraints that restrict the maximum number of intermediate routers along each communication path. Different possibilities to model the GHMSTP as an integer linear program and strengthening valid inequalities are studied. The obtained formulations are compared theoretically, i.e., by means of their linear programming relaxation. In addition, branch-and-cut approaches based on these formulations are developed and compared in a computational study. (C) 2015 Elsevier Ltd. All rights reserved.

引用

页码：1 / 18

页数：18

共 34 条

[1]

[Anonymous], 2001, THESIS U LIBRE BRUXE

[2]

[Anonymous], 2006, Handbook of Optimization in Telecommunications

[3] Benders Decomposition for the Hop-Constrained Survivable Network Design Problem [J].

Botton, Quentin ;

Fortz, Bernard ;

Gouveia, Luis ;

Poss, Michael .

INFORMS JOURNAL ON COMPUTING, 2013, 25 (01) :13-26

[4] On implementing the push-relabel method for the maximum flow problem [J].

Cherkassky, BV ;

Goldberg, AV .

ALGORITHMICA, 1997, 19 (04) :390-410

[5] The 2-hop spanning tree problem [J].

Dahl, G .

OPERATIONS RESEARCH LETTERS, 1998, 23 (1-2) :21-26

[6] The Generalized Minimum Spanning Tree Problem:: Polyhedral analysis and branch-and-cut algorithm [J].

Feremans, C ;

Labbé, M ;

Laporte, G .

NETWORKS, 2004, 43 (02) :71-86

[7] A branch-and-cut algorithm for the symmetric generalized traveling salesman problem [J].

Fischetti, M ;

Gonzalez, JJS ;

Toth, P .

OPERATIONS RESEARCH, 1997, 45 (03) :378-394

[8] Heuristic search for the generalized minimum spanning tree problem [J].

Golden, B ;

Raghavan, S ;

Stanojevic, D .

INFORMS JOURNAL ON COMPUTING, 2005, 17 (03) :290-304

[9] Multicommodity flow models for spanning trees with hop constraints [J].

Gouveia, L .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 95 (01) :178-190

[10] USING THE MILLER-TUCKER-ZEMLIN CONSTRAINTS TO FORMULATE A MINIMAL SPANNING TREE PROBLEM WITH HOP CONSTRAINTS [J].

GOUVEIA, L .

COMPUTERS & OPERATIONS RESEARCH, 1995, 22 (09) :959-970

← 1 2 3 4 →