Example: 'Computes the optimal minimum cost access-to-core network'

Brief description

Given a set of access nodes, this algorithm computes the subset of access nodes which have a core node located next to it (in the same place), and the links access-to-core nodes, so that the network cost is minimized. This cost is given by a cost per core node (always 1) plus a cost per link, given by the product of link distance and the user-defined parameter linkCostPerKm. Access-core link capacities are fixed to the user-defined parameter linkCapacities. A core node cannot be connected to more than K_max access nodes, a user-defined parameter. This problem is modeled as a ILP and optimally solved using a solver.

Algorithm description table

Algorithm inputs

Requires a set of nodes within the netPlan object.

Algorithm parameters:

  • K_max: Maximum number of access nodes that can be connected to a core node. Default: 5
  • linkCapacities: The capacities to set in the links. Default: 100
  • linkCostPerKm: The cost per km of the links between access and core nodes. 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
Algorithm outputsNew links are added to netPlan object. Any previous links are removed.
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_nodeLocationILP.java

Detailed description

The algorithm solves the following formulation:

Given:

  • \( N \): Set of nodes.
  • \( c_{ij} \): Cost per link between nodes \( i \) and \( j \). It is given by the product of the physical distance between nodes and the linkCostPerKm parameter.

Find:

  • \( z_{j} \): Binary variables indicating whether node \( j \) is a core node.
  • \( e_{ij} \): Binary variables indicating whether node \( i \) is connected to node \( j \).

\( \text{minimize } \left( \sum_{j \in N} z_{j} + \sum_{i \in N}\sum_{j \in N} c_{ij} \cdot e_{ij} \right) \text{ subject to: } \\
\sum_{j \in N} e_ij = 1 \quad \forall i \in N\\ \sum_{i \in N} e_ij <= K_{max} \cdot z_{j} \quad \forall j \in N\\ z_{j} \in \lbrace 0 , 1 \rbrace \quad \forall j \in N\\ e_{ij} \in \lbrace 0 , 1 \rbrace \quad \forall (i,j) \in N\\ \)