Example: 'Maximum idle bottleneck capacity routing, flow-link formulation'

Brief description

Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the network congestion, with or without the constraint of non-bifurcated routing.

In this algorithm, congestion is minimized by maximizing the idle link capacity in the bottleneck (the link with less idle capacity).

Algorithm description table

Algorithm inputs

Requires a topology (nodes and links) and a demand set within the netPlan object.

Algorithm parameters:

  • nonBifurcated: "true" if the routing is constrained to be non-bifurcated, "false" otherwise. Default: "false"
  • solverName: The solver name to be used by JOM. Default: "glpk"
  • solverLibraryName: The solver library full or relative path, to be used by JOM. Leave blank to use JOM default. Default: blank
Algorithm outputsThe routes are added to netPlan object. No protection segments/routes are defined. Any previous routes are removed.
Required librariesJOM library for solving the optimization problem
KeywordsFlow assignment (FA), JOM, LP formulation, MILP formulation
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeFA_maxBottleneckIdleCapacity_xde.java

Detailed description

The algorithm solves the following formulation:

Given:

  • \( 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.
  • \( 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, \( u_e \) the link capacity (in the same units as the offered traffic). For each node \( n \in N \), \( \delta^+(n) \) and \( \delta^-(n) \) denote the set of links outgoing and incoming node \( n \), respectively.

Find:

  • \( x_{de} , d \in D, e \in E \): Fraction \( \in [ 0 , 1 ] \) of the traffic of demand \( d \) that traverses link \( e \). If the routing is non-bifurcated, this variable is constrained to get integer numbers: \( x_{de} \in \lbrace 0 , 1 \rbrace \).
  • \( \bar u \): Idle capacity in the bottleneck link.

\( \text{maximize } \left( \bar u \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 u_e - \bar u \quad \forall e \in E \\ 0 \leq x_{de} \leq 1 \quad \forall d \in D, e \in E \\ x_{de} \in \lbrace 0 , 1 \rbrace \quad \forall d \in D, e \in E \text{ (if routing is non-bifurcated) } \)