[PDF] [PDF] Hierarchical Network Design - DTU Informatics

View - Download [PDF] Hierarchical Network Design - DTU Informatics

Previous PDF

Next PDF

Hierarchical Network Design

Tommy Thomadsen

Kongens Lyngby 2005

IMM-PHD-2005-149

Technical University of Denmark

Informatics and Mathematical Modelling

Building 321, DK-2800 Kongens Lyngby, Denmark

Phone +45 45253351, Fax +45 45882673

reception@imm.dtu.dk www.imm.dtu.dk

IMM-PHD: ISSN 0909-3192

Summary

Communication networks are immensely important today, since both companies and individuals use numerous services that rely on them. This thesis considers the design of hierarchical (communication) networks. Hierarchical networks consist of layers of networks and are well-suited for coping with changing and increasing demands. Two-layernetworks consist of one backbone network, which interconnects cluster networks. The clusters consist of nodes and links, which connect the nodes. One node in each cluster is a hub node, and the backbone interconnects the hub nodes of each cluster and thus the clusters. The design of hierarchical networks involves clustering of nodes, hub selection, and network design, i.e. selection of links and routing of ows. Hierarchical networks have been in use for decades, but integrated design of these networks has only been considered for very special types of networks. The thesis investigates models for hierarchical network design and methods used to design such networks. In addition, ring network design is considered, since ring networks commonly appear in the design of hierarchical networks. The thesis introduces hierarchical networks, including a classication scheme of dierent types of hierarchical networks. This is supplemented by a review of ring network design problems and a presentation of a model allowing for model- ing most hierarchical networks. We use methods based on linear programming to design the hierarchical networks. Thus, a brief introduction to the various linear programming based methods is included. The thesis is thus suitable as a foundation for study of design of hierarchical networks. The major contribution of the thesis consists of seven papers which are included ii in the appendix. The papers address hierarchical network design and/or ring network design. The papers have all been submitted for journals, and except for two papers, are awaiting review. The papers are mostly concerned with optimal methods and, in a few cases, heuristics for designing hierarchical and ring networks. All papers develop bounds which are used in the optimal methods and for comparison. Finally, computational results are reported.

Resume

Kommunikationsnetvrk har enorm betydning i dag, da enkeltpersoner og virk- somheder anvender utallige tjenester, som afhnger af kommunikationsnetvrk- ene. Denne afhandling omhandler design af hierarkiske (kommunikations-) net- vrk. Hierarkiske netvrk er lagdelte og er velegnede til at handtere ndringer og gede i krav til bandbredde. Netvrk med to niveauer bestar af et back- bone netvrk som forbinder klynger af netvrksknuder. Klyngerne bestar af netvrksknuder og forbindelser mellem netvrksknuderne internt i klyngen. I hver klynge er en af netvrksknuderne udpeget som hoved-netvrksknuden, dvs. den har forbindelse til backbone netvrket. Backbone netvrket forbinder hoved-netvrksknuderne og dermed klyngerne. For at designe et hierarkisk netvrk, skal der tages stilling til hvilke netvrksknuder der er i hvilken klynge, hoved-netvrksknuderne skal udvlges, netvrksknuderne skal forbindes bade i klyngerne og i backbone netvrket, og trak skal rutes i netvrket. Hierarkiske netvrk har vret anvendt i artier, men design af disse netvrk er kun blevet undersgt for specielle netvrkstyper. Denne afhandling undersger modeller til design af hierarkiske netvrk og metoder der kan anvendes til at de- signe hierarkiske netvrk. Derudover undersges ring netvrk, da ring netvrk ofte forekommer i design af hierarkiske netvrk. Afhandlingen introducerer hierarkiske netvrk, inklusive et klassikationsskema af de forskellige typer af hierarkiske netvrk. Dette bliver suppleret med en gennemgang af ring netvrk problemer og en prsentation af en generel model, der tillader modellering af de este hierarkiske netvrk. Metoder baseret pa liner programmering introduceres, idet de anvendes til design af hierarkiske netvrk. Afhandlingen kan saledes danne grundlag for et studie af design af hierarkiske netvrk. iv Afhandlings vigtigste bidrag bestar af syv artikler, der er inkluderet i appendiks. Artiklerne handler om design af hierarkisk netvrk og ring netvrk. Artiklerne er alle indsendt til videnskablige journaler og afventer bedmmelse, bortset fra to artikler, der allerede er blevet accepteret. Artiklerne beskriver oftest optimale metoder og i enkelte tilflde heuristikker til at design hierarkiske netvrk samt ring netvrk. I alle tilflde er der udviklet grnser, der kan anvendes enten til sammenligning eller indlejret i de optimale metoder. Endelig prsenteres resultater for testkrsler af metoderne.

Preface

This thesis was prepared at Informatics and Mathematical Modelling, the Tech- nical University of Denmark in partial fulllment of the requirements for ac- quiring the Ph.D. degree. The thesis considers optimization of communication networks with more lay- ers denoted hierarchical networks. The Ph.D. project has been supervised by professor Jens Clausen. The thesis consists of an introduction to the project and a collection of seven research papers prepared during the period 2002{2005.

Lyngby, May 2005

Tommy Thomadsen

vi

Papers included in the thesis

A Vicky Mak, Tommy Thomadsen. Facets for the Cardinality Constrained Quadratic KnapsackProblem and the Quadratic Selective TravellingSales- man Problem, 2004. Submitted forJ. of Combinatorial Optimization. B Tommy Thomadsen, Thomas Stidsen. A Branch-and-Cut Algorithm for the Quadratic Selective Travelling Salesman Problem, 2003. Submitted forTelecommunication Systems. C Tommy Thomadsen, Thomas Stidsen. Hierarchical Ring Network Design Using Branch-and-Price, 2005.Telecommunication Systems, Volume 29,

Issue 1, pp. 61{76.

D Thomas Stidsen, Tommy Thomadsen. Joint Routing and ProtectionUsing p-cycles, 2004. Submitted forEuropean Journal of Operational Research. E Tommy Thomadsen, Thomas Stidsen. The Generalized Fixed-Charge Network Design Problem, 2004. Accepted for publication inComputers and Operations Research. F Tommy Thomadsen, Jesper Larsen. The Two-Layered Fully Intercon- nected Network Design Problem { Models and an Exact Approach, 2005.

Submitted forComputers and Operations Research.

G Tommy Thomadsen. Design of Two-Layered Fixed Charge Networks,

2005. Submitted forNetworks.

viii

Acknowledgments

I would like to thank my wife Hanne for supporting me during the 3 years of work, and for giving me the opportunity to occasionally spent way too much time on working. Also I thank my daughter Laura for giving me the reason and opportunity to take on parental leave for 3 months, when it was needed the most. I thank my colleagues at the operations research section for creating an invalu- able work environment. I thank my supervisor Jens Clausen for being there when needed and especially I thank Thomas K. Stidsen for helpful discussions and feedback. The sometimes loud-voiced discussions have been, if not neces- sary, very benecial. Finally I thank other colleagues for enduring all the noise we made and for closing the door when we forgot to. x

Contents

Summary i

Resume iii

Preface v

Papers included in the thesis vii

Acknowledgments ix

1 Introduction 1

1.1 HierarchicalNetworks ........................ 2

1.2 Subproblems in Hierarchical Network Design . . . . . . . . . . . 3

1.3 OutlineoftheThesis......................... 4

2 Ring Network Design Problems 7

2.1 The Travelling Salesman Problem . . . . . . . . . . . . . . . . . . 8

xii CONTENTS

2.2 TSPwithOptionalNodes...................... 8

2.3 TSPwithQuadraticCostsandRevenues ............. 12

3 Hierarchical Network Design Problems 15

3.1 TheFixedChargeNetworkDesignProblem............ 15

3.2 The Basic Model for Hierarchical Network Design Problems . . . 17

3.3 An Extended Model for Hierarchical Network Design Problems . 18

3.4 Topology Constraints on the Clusters . . . . . . . . . . . . . . . . 19

3.5 Topology Constraints on the Backbone . . . . . . . . . . . . . . . 20

3.6 MoreHubs .............................. 21

3.7 Usingthemodels........................... 22

3.8 RelatedPapers............................ 22

4 Linear Programming Based Methods 23

4.1 The Linear Programming Relaxation . . . . . . . . . . . . . . . . 23

4.2 Branch-and-Bound.......................... 24

4.3 CuttingPlaneandBranch-and-Cut................. 25

4.4 ColumnGenerationandBranch-and-Price............. 26

4.5 Branch-Cut-and-Price ........................ 28

5 Papers in the Thesis 29

5.1 Paper A: Facets for the Cardinality Constrained Quadratic Knap-

sack Problem and the Quadratic Selective Travelling Salesman

Problem................................ 29

CONTENTS xiii

5.2 Paper B: A Branch-and-Cut Algorithm for the Quadratic Selec-

tive Travelling Salesman Problem . . . . . . . . . . . . . . . . . . 30

5.3 Paper C: Hierarchical Ring Network Design Using Branch-and-

Price.................................. 30

5.4 Paper D: Joint Routing and Protection Usingp-cycles . . . . . . 31

5.5 Paper E: The Generalized Fixed-Charge Network Design Problem 31

5.6 Paper F: The Two-Layered Fully Interconnected Network Design

Problem { Models and an Exact Approach . . . . . . . . . . . . . 32

5.7 Paper G: Design of Two-Layered Fixed Charge Networks . . . . 33

6Conclusion 35

6.1 Summary ............................... 35

6.2 MainContributions.......................... 36

6.3 FutureWork ............................. 37

A Facets for the Cardinality Constrained Quadratic Knapsack Problem and the Quadratic Selective Travelling Salesman Prob- lem 39

A.1 Introduction.............................. 40

A.2 Integer Programming Model and the Polyhedra . . . . . . . . . . 42 A.3 PolyhedralresultsfortheQKpolytope .............. 44 A.4 PolyhedralresultsfortheQSTSpolytope ............. 48

A.5 Conclusion .............................. 56

B A Branch-and-Cut Algorithm for the Quadratic Selective Trav- elling Salesman Problem 59

B.1 Introduction.............................. 61

xiv CONTENTS

B.2 TheModel .............................. 62

B.3 Branch-and-Cut Algorithm . . . . . . . . . . . . . . . . . . . . . 66

B.4 Heuristics............................... 69

B.5 ComputationalResults........................ 71

B.6 Conclusions.............................. 80

C Hierarchical Ring Network Design Using Branch-and-Price 83

C.1 Introduction.............................. 84

C.2 Previouswork............................. 87

C.3 TheModiedHRNProblem..................... 88

C.4 TheProblems............................. 90

C.5 TheBranch-and-PriceAlgorithm.................. 93 C.6 ComputationalResults........................ 96

C.7 Conclusion ..............................100

D Joint Routing and Protection Usingp-cycles 103

D.1 Introduction..............................105

D.2 Thep-cycleProtectionMethod...................106 D.3 Previous Work onp-cyclePlanning.................108 D.4 SolutionMethodology ........................109 D.5 ResultsandDiscussion........................117

D.6 Conclusion ..............................122

E The Generalized Fixed-Charge Network Design Problem 125

CONTENTS xv

E.1 Introduction..............................126

E.2 RelatedProblems...........................127

E.3 AMIPModelfortheGFCNDProblem ..............129

E.4 SolvingtheGFCNDproblem ....................131quotesdbs_dbs17.pdfusesText_23

[PDF] hierarchical regression table apa

[PDF] hierarchical structure journal article

[PDF] hierarchy java example

[PDF] hierarchy of law reports

[PDF] hifly a321

[PDF] hifly a380 interior

[PDF] hifly a380 model

[PDF] high appellate court definition

[PDF] high court

[PDF] high efficiency boiler

[PDF] high level french adjectives

[PDF] high net worth individuals survey

[PDF] high paid jobs in demand uk

[PDF] high paying jobs in high demand uk

[PDF] high school admission essay examples about yourself