Chapter 10

Network Design Problems: Models and Applications

10.1. Introduction

In Chapter 9, we introduced the conceptual basis of network design problems, and we illustrated this with the help of a generic model:

Sample problem CFA: capacitated flow assignment.

{Find, on an initial network G = (X,E), which defines a support topology, an infrastructure vector z ≥ 0 ∈ Z and a multiflow f = (fi i in I) ≥ 0 such that:

C1(z) (structural constraints on z, which can be discrete or real and constrained for security reasons; we could for example require of z that it allows the transit of a certain type of message by at least two arc disjoint paths).
For every arc e in E, ze ≥ f*e or f* returns an aggregate vector (more often than not the sum) constructed from the components of the multiflow f
Each component fi of the multiflow f transfers a certain average demand Mi from a set of origin vertices Oi to a set of destination vertices Di.

Zmin = U(z) (installation cost) + V(z,f) (operational cost linked to y) + W(z,f) (measure of service failure associated with y) is the smallest possible.}

We then proposed a taxonomy of network design problems, based on the fact that:

– the importance taken by the quality of service (QoS) leads us to introduce performance functions W(x,f) that are more and more complex;
– taking into account the variations in traffic over time leads to the introduction of dynamic or timed networks [ARO 89, CHAR 96, YAG 73];
– introducing real and virtual networks ...

Get Applications of Combinatorial Optimization, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.