Network Design Optimization: Core Node Placement Model

Optimization Problem Setup and Initialization

The following code initializes parameters and sets up the optimization problem structure using Net2Plan's framework.

Initialization of Parameters and Variables

final double C = Double.parseDouble(algorithmParameters.get("C"));
final int K = Integer.parseInt(algorithmParameters.get("K"));
netPlan.removeAllLinks();

OptimizationProblem op = new OptimizationProblem();
final int N = netPlan.getNumberOfNodes();

// Decision Variables
op.addDecisionVariable("z_j", true, new int[] {1, N}, 0, 1); 
// z_j: 1 if location j has a core node (Array of N positions)

op.addDecisionVariable("e_ij", true, new int[] {N, N}, 0, 1); 
// e_ij: 1 if access node at location i is connected to a core node in j

Defining Input Parameters and Objective Function

We define the costs, capacity, and distance matrix as input parameters, followed by the objective function.

/* Adding input parameters */
op.setInputParameter("C", C);
op.setInputParameter("K", K);
op.setInputParameter("c_ij", netPlan.getMatrixNode2NodeEuclideanDistance());

op.setObjectiveFunction("minimize", "C * sum(z_j) + sum(c_ij .* e_ij)");

Constraint Implementation

Access Node Connectivity Constraint

Each access node i must be connected to exactly one core node j.

for (Node i : netPlan.getNodes())
{
    op.setInputParameter("i", i.getIndex());
    op.addConstraint("sum(e_ij(i,all)) == 1"); 
    // Constraint: Access node i connects to exactly one core node
}

Core Node Capacity Constraint

This constraint ensures that a core node j receives 0 access links if it does not exist (z_j=0), and at most K access links if it exists (z_j=1).

for (Node j : netPlan.getNodes())
{
    op.setInputParameter("j", j.getIndex());
    op.addConstraint("sum(e_ij(all,j)) <= K * z_j(j)");
}

Solving the Optimization Problem and Processing Results

Executing the Solver

The problem is solved using the GLPK solver. An exception is thrown if an optimal solution is not found.

/* Calling the solver to solve the problem */
op.solve("glpk");

if (!op.solutionIsOptimal()) 
    throw new Net2PlanException("The solution is not optimal");
/* If the solution is not optimal, throw an exception */

Processing Results and Network Update

If the solution is optimal, the primal solutions for the decision variables z_j and e_ij are retrieved. These results are then used to update the network design by adding the necessary access links (which are non-bidirectional).

/* If optimal, retrieve the solution in 1D and 2D arrays */
final double[] z_j = op.getPrimalSolution("z_j").to1DArray();
final double[][] e_ij = (double[][]) op.getPrimalSolution("e_ij").toArray();

/* Store the access links in the design (links are not bidirectional) */
for (Node i : netPlan.getNodes()) 
    for (Node j : netPlan.getNodes())
        if ((i != j) && (e_ij[i.getIndex()][j.getIndex()] == 1))
            netPlan.addLink(i, j, 1, netPlan.getNodePairEuclideanDistance(i, j), 200000, null);

Final Result Calculation and Output

/* Compute the total number of core nodes */
int numCoreNodes = 0; 
for (int n = 0; n < N; n++) 
    numCoreNodes += z_j[n];

return "Ok! Number of core nodes: " + numCoreNodes + ", total cost: " + op.getOptimalCost();