Point-to-point vs. hub-and-spoke. Questions of network design are real and involve many billions of dollars. Yet little is known about optimizing design - nearly all work concerns optimizing flow assuming a given design. This foundational book tackles optimization of network structure itself, deriving comprehensible and realistic design principles. With fixed material cost rates, a natural class of models implies the optimality of direct source-destination connections, but considerations of variable load and environmental intrusion then enforce trunking in the optimal design, producing an arterial or hierarchical net. Its determination requires a continuum formulation, which can however be simplified once a discrete structure begins to emerge. Connections are made with the masterly work of Bendsøe and Sigmund on optimal mechanical structures and also with neural, processing and communication networks, including those of the Internet and the Worldwide Web. Technical appendices are provided on random graphs and polymer models and on the Klimov index.
Author(s): Peter Whittle
Series: Cambridge Series in Statistical and Probabilistic Mathematics
Edition: 1
Publisher: Cambridge University Press
Year: 2007
Language: English
Pages: 283
Half-title......Page 3
Series-title......Page 4
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Acknowledgements......Page 10
Conventions on notation......Page 11
Whither? Why?......Page 13
I Distributional networks......Page 19
1.1 The setting......Page 21
1.2 Flow optimisation......Page 22
1.3 Seminvariantly scaled costs......Page 24
1.4 A first consideration of optimal design......Page 26
1.5 The dual formulation......Page 31
1.6 The primal and dual forms......Page 32
1.7 The multipliers as marginal prices......Page 33
1.8 Balance of supply and demand......Page 34
2.1 The primal problem......Page 36
2.2 The dual formulation......Page 38
2.3 Evolutionary algorithms......Page 40
2.4 A trivial continuum example......Page 41
2.5 Optimal cooling......Page 42
2.7 Nonuniform spaces......Page 51
3.1 Reduction of the problem......Page 54
3.2 The dual and its interpretation......Page 56
3.3 An alternative formulation......Page 58
4.1 Variable loading and the primal problem......Page 59
4.2 Internal nodes and trunking......Page 61
4.3 Optimality and load splitting......Page 65
4.4 Variable loading in the dual formulation......Page 66
4.5 Degree of trunking......Page 68
4.6 Trunking from a continuous source line......Page 69
4.7 Evolutionary algorithms......Page 73
4.8 Node migration and node splitting......Page 74
4.9 The case of general convex Phi......Page 76
5.1 Incentives to trunking......Page 78
5.2 Other consequences of cost concavity......Page 80
5.3 The combination of environmental penalty and variable load......Page 82
5.4 Hierarchical structure......Page 84
5.5 The outflow function......Page 86
5.6 Optimisation of the trunking rate......Page 89
5.7 The multi-dimensional case......Page 93
6.1 The setting......Page 97
6.2 Structural considerations......Page 98
6.3 Congestion: the queueing analogue......Page 99
6.4 Congestion: fluid and discrete models......Page 101
6.5 When motorists choose......Page 104
7.1 Force and deformation; stress and strain......Page 107
7.2 Braced frameworks: formulation......Page 111
7.3 Reduction of the primal problem......Page 113
7.4 The dual form of the problem......Page 114
7.5 The dual field: Hencky–Prandtl nets......Page 117
7.6 Some examples of Michell structures......Page 120
7.7 The shaping of bone structure......Page 125
8.1 Solid materials......Page 128
8.2 Examples......Page 131
8.3 Expanded materials......Page 134
8.4 The literature on structural optimisation......Page 137
9 Structure design for variable load......Page 138
9.1 Return to the coat-hook......Page 139
9.2 Numerical experience......Page 142
9.3 The shaping of bone structure......Page 144
9.4 Buckling......Page 145
II Artificial neural networks......Page 147
10.1 The McCulloch–Pitts net......Page 149
10.2 Back-propagation and Hebb's rule......Page 151
10.3 Linear least-squares approximation......Page 154
11.1 Recognition, feedback and memory......Page 158
11.2 The Hamming net......Page 160
11.3 The probability-maximising algorithm......Page 162
11.4 The PMA with compound traces......Page 164
11.5 Comparisons with the olfactory system......Page 166
12.1 The Freeman model of the neuron......Page 170
12.2 The Freeman oscillator......Page 172
12.3 Oscillation in memory arrays......Page 174
III Processing networks......Page 179
13.1 The simple queue......Page 181
13.2 The multi-station case; deterministic treatment......Page 183
13.3 Jackson networks......Page 184
13.4 Optimisation of effort distribution......Page 186
13.5 Queueing networks more generally......Page 187
13.6 A small coda......Page 189
14.1 The fluid and Markov models......Page 191
14.2 The Gittins–Klimov index......Page 193
14.3 Examples......Page 195
14.4 Performance of the index policy......Page 197
14.5 Control with fixed work-station resources......Page 199
IV Communication networks......Page 203
15.1 The linear programming formulation......Page 205
15.2 Design optimisation for a given configuration......Page 207
15.3 A free optimisation......Page 209
16.1 A single exchange; Erlang's formula......Page 211
16.2 Admission control for a single exchange......Page 213
16.3 Equilibrium and asymptotics for the network......Page 215
16.4 Refinements of the asymptotics......Page 218
16.5 Self-regulation for the network......Page 220
17 Operation of the Internet......Page 223
17.1 Some background......Page 224
17.2 A stable regulation rule......Page 227
17.3 An adaptive rate control......Page 228
18.1 Random graphs and the Web......Page 231
18.2 Evolution of the scale-free network......Page 232
18.3 Graph properties......Page 233
18.4 Emulation and the power law......Page 235
A1.1 The limit outflow density......Page 239
A1.2 Outflow and withinflow......Page 240
A1.3 Character of the outflow density......Page 241
A1.4 Flows between cells......Page 242
A1.5 Cubic examples......Page 244
A2.1 Bandit processes......Page 246
A2.2 Tax processes......Page 248
A2.3 Adaptation to fixed work-stations......Page 250
A3.1 The zeroth-order model......Page 252
A3.2 The first-shell model: unit statistics......Page 254
A3.3 Polymer statistics......Page 257
A3.4 Nothing but trees......Page 260
A3.5 The branching analogue; Potts criticality......Page 267
A3.6 The distribution of degree......Page 270
A3.7 Literature and further directions......Page 271
References......Page 273
Index......Page 280
