Brief description
Given a network topology, and the offered traffic, this algorithm obtains the traffic routing and the (modular) capacities in the links that minimizes the link costs. The capacity of a link is constrained to be the aggregation of integer multiples of modules of capacities {0.15, 0.6, 2.4, 9.6} Gbps, and prices {1, 2, 4, 8} monetary units. Link utilization is limited by the user-defined parameter rhoMax
Algorithm description table
| Algorithm inputs | Requires a topology (nodes and links) and a demand set within the netPlan object. Algorithm parameters:
|
|---|---|
| Algorithm outputs | Link capacities and traffic routing updated within the netPlan object. |
| Required libraries | JOM library for solving the optimization problem |
| Keywords | Capacity assignment (CA), Flow assignment (FA), JOM, MILP formulation |
| Authors | Pablo Pavón Mariño, José Luis Izquierdo Zaragoza |
| Date | March 2013 |
| Code | CFA_minCostModularCapacities_xde.java |
Detailed description
The algorithm solves the following formulation:
Given:
- \( G(N,E) \): The network topology, where \( N \) is the set of nodes, and \( E \) the set of unidirectional network links. For each link \( e \in E \), \( a(e) \) and \( b(e) \) denote its input and output nodes.
- \( D \): The set of demands comprising the offered traffic. For each demand \( d \in D \), \( h_d \) is the demand volume, and \( a(d) \) and \( b(d) \) denote the input and output node of the demand.
- \( \rho_{max} \): Maximum utilization allowed in the links.
- \( I \): The set of capacity modules allowed demands comprising the offered traffic. For each capacity module \( i \in D \), \( u_i \) is the capacity value (in Erlangs), and \( p_i \) denote the cost of installing that capacity.
Find:
- \( x_{de} , d \in D, e \in E \): Fraction \( \in [ 0 , 1 ] \) of the traffic of demand \( d \) that traverses link \( e \).
- \( n_{ei} , e \in E, i \in I \): Equal to 1 if capacity module \( i \) is installed on link \( e \), otherwise it is equal to 0.
\(
\text{minimize } \left( \sum_{e\in E}\sum_{i\in I}n_{ei}\cdot p_i \right) \text{ subject to: } \\
\sum_{e \in \delta^+(n)} x_{de} - \sum_{e \in \delta^-(n)} x_{de} = \begin{cases}
1, &\text{if $n = a(d)$} \\
-1, &\text{if $n = b(d)$} \\
0, &\text{otherwise}
\end{cases}
\quad \forall n \in N, d \in D \\
\sum_d h_d x_{de} \leq \rho_{max}\cdot u_i\cdot n_{ei} \quad \forall e \in E \\
0 \leq x_{de} \leq 1 \quad \forall d \in D, e \in E \\
n_{ei} \in \lbrace 0 , 1 \rbrace \quad \forall e \in E
\)
