Java Network Optimization: Source Routing and Link Capacity Design

Network Optimization with Source Routing in Java

The following Java code configures source routing, creates links between all node pairs, and solves a cost minimization problem using GLPK.

Source Routing and Link Creation

netPlan.setRoutingType(RoutingType.SOURCE_ROUTING);
for (Node n1 : netPlan.getNodes())
{
    for (Node n2 : netPlan.getNodes())
    {
        if (n1 != n2)
        {
            netPlan.addLink(n1, n2, 0, netPlan.getNodePairEuclideanDistance(n1, n2), 200000, null);
        }
    }
}
final int D = netPlan.getNumberOfDemands();
final int E = netPlan.getNumberOfLinks();

Decision Variables

op.addDecisionVariable("z_e", false, new int[]{1, E}, 0, Double.MAX_VALUE); /* variable for each existing link, we need to know the number of these (see line above) */
op.addDecisionVariable("x_de", false, new int[]{D, E}, 0, Double.MAX_VALUE); /* traffic of demand D that flows through link E */
op.addDecisionVariable("u_e", false, new int[]{1, E}, 0, maximunLinkCapacity);

Input Parameters and Objective Function

The following parameters are input values for the objective function that are not decision variables:

op.setInputParameter("d_e", netPlan.getVectorLinkLengthInKm(), "row");
op.setInputParameter("c_km", costPerKm);
op.setInputParameter("c_Gbps", costPerGbps);
op.setObjectiveFunction("minimize", "c_km * d_e * z_e' + c_Gbps * sum(u_e)");
op.setInputParameter("U", maximunLinkCapacity);

Capacity Constraints

for (Link e : netPlan.getLinks())
{
    op.setInputParameter("e", e.getIndex());
    op.addConstraint("u_e(e) <= U * z_e(e)");
}

Flow Conservation Constraints

for (Node n : netPlan.getNodes())
{
    op.setInputParameter("deltaPlus", NetPlan.getIndexes(n.getOutgoingLinks()), "row");
    op.setInputParameter("deltaMinus", NetPlan.getIndexes(n.getIncomingLinks()), "row");
    for (Demand d : netPlan.getDemands())
    {
        op.setInputParameter("d", d.getIndex());
        op.setInputParameter("h_d", d.getOfferedTraffic());
        if (n == d.getIngressNode())
            op.addConstraint("sum(x_de(d,deltaPlus)) - sum(x_de(d,deltaMinus)) == h_d");
        else if (n == d.getEgressNode())
            op.addConstraint("sum(x_de(d,deltaPlus)) - sum(x_de(d,deltaMinus)) == -h_d");
        else
            op.addConstraint("sum(x_de(d,deltaPlus)) - sum(x_de(d,deltaMinus)) == 0");
    }
}

Link Traffic Constraints

for (Link e : netPlan.getLinks())
{
    op.setInputParameter("e", e.getIndex());
    op.addConstraint("sum(x_de(all, e)) <= u_e(e)"); /* all links */
}

Solving and Applying the Solution

op.solve("glpk", "maxSolverTimeInSeconds", 10);
if (!op.solutionIsFeasible())
    throw new Net2PlanException("A feasible solution was not found");

final DoubleMatrix2D x_de = op.getPrimalSolution("x_de").view2D();
netPlan.setRoutingFromDemandLinkCarriedTraffic(x_de, false, false);

final double[] u_e = op.getPrimalSolution("u_e").to1DArray();
for (Link e : netPlan.getLinks())
    e.setCapacity(u_e[e.getIndex()]);
netPlan.removeAllLinksUnused(0.01);
return "Ok!";
}