Hierarchical network design

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

[email protected]

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-layer networks 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 flows.

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 classification scheme of

different 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.

Resum´e

Kommunikationsnetværk har enorm betydning i dag, da enkeltpersoner og virk￾somheder anvender utallige tjenester, som afhænger af kommunikationsnetværk￾ene. Denne afhandling omhandler design af hierarkiske (kommunikations-) net￾værk. Hierarkiske netværk er lagdelte og er velegnede til at h˚andtere ændringer

og øgede i krav til b˚andbredde. Netværk med to niveauer best˚ar af et back￾bone netværk som forbinder klynger af netværksknuder. Klyngerne best˚ar af

netværksknuder og forbindelser mellem netværksknuderne internt i klyngen. I

hver klynge er en af netværksknuderne udpeget som hoved-netværksknuden,

dvs. den har forbindelse til backbone netværket. Backbone netværket forbinder

hoved-netværksknuderne og dermed klyngerne. For at designe et hierarkisk

netværk, skal der tages stilling til hvilke netværksknuder der er i hvilken klynge,

hoved-netværksknuderne skal udvælges, netværksknuderne skal forbindes b˚ade

i klyngerne og i backbone netværket, og trafik skal rutes i netværket.

Hierarkiske netværk har været anvendt i ˚artier, men design af disse netværk er

kun blevet undersøgt for specielle netværkstyper. Denne afhandling undersøger

modeller til design af hierarkiske netværk og metoder der kan anvendes til at de￾signe hierarkiske netværk. Derudover undersøges ring netværk, da ring netværk

ofte forekommer i design af hierarkiske netværk.

Afhandlingen introducerer hierarkiske netværk, inklusive et klassifikationsskema

af de forskellige typer af hierarkiske netværk. Dette bliver suppleret med en

gennemgang af ring netværk problemer og en præsentation af en generel model,

der tillader modellering af de fleste hierarkiske netværk. Metoder baseret p˚a

lineær programmering introduceres, idet de anvendes til design af hierarkiske

netværk. Afhandlingen kan s˚aledes danne grundlag for et studie af design af

hierarkiske netværk.

iv

Afhandlings vigtigste bidrag best˚ar af syv artikler, der er inkluderet i appendiks.

Artiklerne handler om design af hierarkisk netværk og ring netværk. Artiklerne

er alle indsendt til videnskablige journaler og afventer bedømmelse, bortset fra

to artikler, der allerede er blevet accepteret. Artiklerne beskriver oftest optimale

metoder og i enkelte tilfælde heuristikker til at design hierarkiske netværk samt

ring netværk. I alle tilfælde er der udviklet grænser, der kan anvendes enten

til sammenligning eller indlejret i de optimale metoder. Endelig præsenteres

resultater for testkørsler af metoderne.

Preface

This thesis was prepared at Informatics and Mathematical Modelling, the Tech￾nical University of Denmark in partial fulfillment 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 Knapsack Problem and the Quadratic Selective Travelling Sales￾man Problem, 2004. Submitted for J. of Combinatorial Optimization.

B Tommy Thomadsen, Thomas Stidsen. A Branch-and-Cut Algorithm for

the Quadratic Selective Travelling Salesman Problem, 2003. Submitted

for Telecommunication 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 Protection Using

p-cycles, 2004. Submitted for European Journal of Operational Research.

E Tommy Thomadsen, Thomas Stidsen. The Generalized Fixed-Charge

Network Design Problem, 2004. Accepted for publication in Computers

and Operations Research.

F Tommy Thomadsen, Jesper Larsen. The Two-Layered Fully Intercon￾nected Network Design Problem – Models and an Exact Approach, 2005.

Submitted for Computers and Operations Research.

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

2005. Submitted for Networks.

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 beneficial. 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

Resum´e iii

Preface v

Papers included in the thesis vii

Acknowledgments ix

1 Introduction 1

1.1 Hierarchical Networks . . . . . . . . . . . . . . . . . . . . . . . . 2

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

1.3 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Ring Network Design Problems 7

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

xii CONTENTS

2.2 TSP with Optional Nodes . . . . . . . . . . . . . . . . . . . . . . 8

2.3 TSP with Quadratic Costs and Revenues . . . . . . . . . . . . . 12

3 Hierarchical Network Design Problems 15

3.1 The Fixed Charge Network Design Problem . . . . . . . . . . . . 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 More Hubs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.7 Using the models . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.8 Related Papers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4 Linear Programming Based Methods 23

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

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

4.3 Cutting Plane and Branch-and-Cut . . . . . . . . . . . . . . . . . 25

4.4 Column Generation and Branch-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 Using p-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

6 Conclusion 35

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

6.2 Main Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 36

6.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Polyhedral results for the QK polytope . . . . . . . . . . . . . . 44

A.4 Polyhedral results for the QSTS polytope . . . . . . . . . . . . . 48

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

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

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