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

*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:

*quality of service*(QoS) leads us to introduce performance functions W(x,f) that are more and more complex;

*dynamic*or

*timed*networks [ARO 89, CHAR 96, YAG 73];

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