Example: 'Computes the optimal bidirectional ring for the network'

Brief description

Given a set of nodes \( N \), this algorithm computes the bidirectional ring with the minimum length (in km) in all its nodes, solving with an ILP (Integer Linear Program) the associated Traveling Salesman Problem (TSP) instance. All the links are set to have the capacity passed as input parameter.

Algorithm description table

Algorithm inputs

A set of nodes within the netPlan is required.

Algorithm parameters:

  • initialNode: Initial node of the spanning tree. Default: 0
  • linkCapacities: The capacities (in Erlangs) to set in the links. Default: 100
  • 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 outputsLinks and their respective capacity values are added to the netPlan object
Required librariesJOM library for solving the optimization problem
KeywordsCapacity assignment (CA), JOM, MILP formulation, Topology assignment (TA)
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeTCA_minLengthBidirectionalRingILP.java

Detailed description

This algorithm is divided into two steps. First, it generates a candidate full-meshed network. Then, it solves a multicommodity flow problem to determine the subset of links to deploy.

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 candidate 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.
  • \( d_e \): Physical distance (in km) for link \( e \).
  • \( D \): Auxiliary set of demands, where each one represents a "virtual" demand from node 0 to each other. For each demand \( d \in D \), \( a(d) \) and \( b(d) \) denote the input (always node 0) and output node of the demand.

Find:

  • \( x_{e}, e \in E \): Binary variables indicating whether or not precomputed link \( e \) is added to the topology.
  • \( x_{de}, d \in D, e \in E \): Variables in range \( [0,1] \) indicating whether or not precomputed link \( e \) is added to the topology. They should be defined as binary variables, but integrality is ensured by other constraints.

\( \text{minimize } \left( \sum_{e \in E} d_{e}\cdot x_{e} \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_{e \in \delta^+(n)} x_{e} == 1 \quad \forall n \in N, e \in E\\ \sum_{e \in \delta^-(n)} x_{e} == 1 \quad \forall n \in N, e \in E\\ \sum_{d \in D} x_{de} \leq x_{e} \quad \forall e \in E \\ x_{e} \in \lbrace 0 , 1 \rbrace \quad \forall e \in E\\ 0 \leq x_{de} \leq 1 \quad \forall d \in D, e \in E \)