Applications of Combinatorial Optimization, 2nd Edition

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 = (f_i 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, z_e ≥ f*_e or f* returns an aggregate vector (more often than not the sum) constructed from the components of the multiflow f

– Each component f_i of the multiflow f transfers a certain average demand Mi from a set of origin vertices O_i to a set of destination vertices D_i.

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