The Network Design Problem

Visualization

The image below visualizes the data created below. In this example we have five cities and six potential edges. We want to create a cost optimal network of the nodes.

Prerequisites

The mathematical Model

Sets: \begin{array}{l} V = \text{Set of }n\text{ nodes}\newline E = \text{Set of edges }(VxV) \end{array}

Parameters: $$d_{i} = \text{Demand of node }i\text{, a negative demand is supply }$$ $$fc_{ij} = \text{Flow cost of edge }i,j\text{, for a single unit }$$ $$dc_{ij} = \text{Design cost of edge }i,j\text{ }$$ $$c_{ij} = \text{Max capacity of edge }i,j\text{ }$$ $$BigM = \text{A large number, f.e. sum of all positive demands }$$

Variables: $$x_{ij} \in \mathbb{R}^+ = \text{Flow of units on edge }i,j\text{ }$$ $$y_{ij} = \begin{cases} 1, \text{ if edge}e\text{ is used }\newline 0, \text{ else} \end{cases}$$

Objective: $$min \sum\limits_{(i,j)\in E} dc_{ij} y_{ij} + fc_{ij} x_{ij}$$

Restrictions: \begin{array}{l} \sum\limits_{{i:(i,j)\in E}} x_{ij} = \sum\limits_{{i:(j,i)\in E}} x_{ji} + d_{j} & \qquad \forall j\in V & \text{(Flow balance, incoming equals outgoing plus demand)}\newline x_{ij} \leq c_{ij} & \qquad \forall i,j\in E & \text{(No edge must exceed its maximum capacity)}\newline y_{ij} \times BigM \geq x_{ij} & \qquad \forall i,j\in E & \text{(A edge is used, if any flow is given)}\newline \end{array}

Create your own Network design problem