Example: 'Computes a minimum cost network with optimized capacities and traffic routing, path-link formulation'

Brief description

Given a set of nodes \( N \), and a traffic demand, this algorithm computes the set of links, their capacities and the routing of traffic that optimally minimizes the network cost given by a fixed cost per link, plus a variable cost with link capacities. Between two nodes, at most one link can exist. The maximum link capacity is U_max, a user-defined parameter. Link fixed cost is given by link distance by fixedCostFactorPerKm, a user-defined parameter. Link variable cost is given by link distance, by link capacity, by variableCostFactorPerKmAndTrafficUnit, a user-defined parameter. The problem is modeled with JOM as a MILP, and optimally solved by a external solver.

Algorithm description table

Algorithm inputs

Requires a set of nodes and a set of traffic demands, both defined within the netPlan object.

Algorithm parameters:

  • fixedCostFactorPerKm: Fixed cost factor per km of a link (the cost of a link of 1 km and 0 capacity). Default: 1
  • 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
  • U_max: The capacities to set in the links. Default: 10
  • variableCostFactorPerKmAndTrafficUnit: Variable cost factor per km and traffic unit of a link (the cost of a link of 1 km and 1 unit of capacity, and 0 of fixed cost). Default: 1
Algorithm outputsNew links and routes are added to netPlan object. No protection segments are defined. Any previous links are removed.
Required librariesJOM library for solving the optimization problem
KeywordsCapacity assignment (CA), Flow assignment (FA), JOM, MILP formulation, Topology assignment (TA)
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeTCFA_minLinkCost.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. Physical distance of link \( e \) is denoted as \( d_{e} \).

Find:

  • \( x_{de} , d \in D, e \in E \): Fraction \( \in [ 0 , 1 ] \) of the traffic of demand \( d \) that traverses link \( e \).
  • \( p_e, e\in E \): Binary variables indicating whether link \( e \) is active.
  • \( u_e, e\in E \): Capacity installed in link \( e \).

\( \text{minimize } \left( \sum_{e\in E} fixedCostFactorPerKm \cdot d_{e} \cdot p_{e} + \\ + variableCostFactorPerKmAndTrafficUnit \cdot d_{e} \cdot u_{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_d h_d x_{de} \leq u_e \quad \forall e \in E \\ u_e \leq U_{max} \cdot p_{e} \quad \forall e \in E \\ 0 \leq x_{de} \leq 1 \quad \forall d \in D, e \in E\\ p_{e} \in \lbrace 0 , 1 \rbrace \quad \forall e \in e \)