001/******************************************************************************* 002 * Copyright (c) 2017 Pablo Pavon Marino and others. 003 * All rights reserved. This program and the accompanying materials 004 * are made available under the terms of the 2-clause BSD License 005 * which accompanies this distribution, and is available at 006 * https://opensource.org/licenses/BSD-2-Clause 007 * 008 * Contributors: 009 * Pablo Pavon Marino and others - initial API and implementation 010 *******************************************************************************/ 011 012 013 014 015 016 017 018 019 020 021package com.net2plan.examples.ocnbook.offline; 022 023import cern.colt.matrix.tdouble.DoubleMatrix1D; 024import cern.colt.matrix.tdouble.DoubleMatrix2D; 025import com.jom.OptimizationProblem; 026import com.net2plan.interfaces.networkDesign.IAlgorithm; 027import com.net2plan.interfaces.networkDesign.Net2PlanException; 028import com.net2plan.interfaces.networkDesign.NetPlan; 029import com.net2plan.interfaces.networkDesign.Node; 030import com.net2plan.utils.InputParameter; 031import com.net2plan.utils.Triple; 032 033import java.util.List; 034import java.util.Map; 035 036/** 037 * This algorithm gives access to several variants of full topology design problems. 038 * @net2plan.description 039 * @net2plan.keywords Topology assignment (TA), Capacity assignment (CA), Flow assignment (FA), Flow-link formulation, JOM 040 * @net2plan.ocnbooksections Section 7.3 041 * @net2plan.inputParameters 042 * @author Pablo Pavon-Marino 043 */ 044public class Offline_tcfa_xdeFormulationsMinLinkCost implements IAlgorithm 045{ 046 private InputParameter topologyType = new InputParameter ("topologyType", "#select# arbitrary-mesh bidirectional-mesh unidirectional-ring bidirectional-ring bidirectional-tree", "The constraints on the link topology: arbitrary topology (no specific constraint), arbitrary bidirectional topology (link from i to j exists iff it exists from j to i), unidirectional ring, bidirectional ring, bidirectional tree"); 047 private InputParameter solverName = new InputParameter ("solverName", "#select# glpk ipopt xpress cplex", "The solver name to be used by JOM. GLPK and IPOPT are free, XPRESS and CPLEX commercial. GLPK, XPRESS and CPLEX solve linear problems w/w.o integer contraints. IPOPT is can solve nonlinear problems (if convex, returns global optimum), but cannot handle integer constraints"); 048 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 049 private InputParameter maxSolverTimeInSeconds = new InputParameter ("maxSolverTimeInSeconds", (double) -1 , "Maximum time granted to the solver to solve the problem. If this time expires, the solver returns the best solution found so far (if a feasible solution is found)"); 050 private InputParameter fixedCostFactorPerKm = new InputParameter ("fixedCostFactorPerKm", (double) 1.0 , "Fixed cost factor per km of a link (the cost of a link of d km and 0 capacity is d times this quantity)" , 0 , true , Double.MAX_VALUE , true); 051 private InputParameter linkPropagationSpeedInKmPerSecond = new InputParameter ("linkPropagationSpeedInKmPerSecond", (double) 200000 , "The propagation speed in km per second of the deployed links" , 0 , false , Double.MAX_VALUE , true); 052 private InputParameter U_max = new InputParameter ("U_max", (double) -1 , "The maximum capacity a link can have. If non positive, there is not limit"); 053 private InputParameter variableCostFactorPerKmAndTrafficUnit = new InputParameter ("variableCostFactorPerKmAndTrafficUnit", (double) 1 , "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)" , 0 , true , Double.MAX_VALUE , true); 054 055 @Override 056 public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters) 057 { 058 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 059 InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters); 060 061 /* Basic checks */ 062 final int N = netPlan.getNumberOfNodes(); 063 final int D = netPlan.getNumberOfDemands(); 064 if (N == 0 || D == 0) throw new Net2PlanException("This algorithm requires a topology and a demand set"); 065 066 /* Initialize some variables */ 067 final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor")); 068 069 /* Create a full mesh of links in the netPlan object */ 070 netPlan.removeAllLinks(); 071 for (Node i : netPlan.getNodes ()) for (Node j : netPlan.getNodes ()) if (i.getId () > j.getId ()) netPlan.addLinkBidirectional(i, j, 1.0 , netPlan.getNodePairEuclideanDistance(i, j), linkPropagationSpeedInKmPerSecond.getDouble() , null); 072 073 /* Compute the distances of the potential links */ 074 final int E_fm = netPlan.getNumberOfLinks(); 075 final DoubleMatrix1D d_e = netPlan.getVectorLinkLengthInKm(); 076 final DoubleMatrix1D h_d = netPlan.getVectorDemandOfferedTraffic(); 077 final DoubleMatrix2D Abid_ee = netPlan.getMatrixLink2LinkBidirectionalityMatrix (); 078 079 /* Create the optimization problem object (JOM library) */ 080 OptimizationProblem op = new OptimizationProblem(); 081 082 /* Set some input parameters */ 083 op.setInputParameter("U_max", U_max.getDouble() > 0? U_max.getDouble() : h_d.zSum()); 084 op.setInputParameter("fc", fixedCostFactorPerKm.getDouble()); 085 op.setInputParameter("vc", variableCostFactorPerKmAndTrafficUnit.getDouble()); 086 op.setInputParameter("h_d", h_d, "row"); 087 op.setInputParameter("d_e", d_e, "row"); 088 op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence()); 089 op.setInputParameter("A_nd", netPlan.getMatrixNodeDemandIncidence()); 090 091 /* Add the decision variables to the problem */ 092 op.addDecisionVariable("z_e", true, new int[] { 1, E_fm }, 0, 1); /* 1 if there is a link installed in the candidate link e */ 093 op.addDecisionVariable("u_e", false, new int[] { 1, E_fm }, 0, U_max.getDouble() <= 0? Double.MAX_VALUE : U_max.getDouble()); /* the capacity installed in the candidate link e, if any */ 094 op.addDecisionVariable("xx_de", false, new int[] { D, E_fm }, 0, 1); /* fraction of the traffic of demand d, that is carried in the candidate link e */ 095 096 /* Sets the objective function */ 097 op.setObjectiveFunction("minimize", "sum(fc * d_e .* z_e) + sum (vc * d_e .* u_e)"); 098 099 /* Compute some matrices required for writing the constraints */ 100 op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints (NxD constraints) */ 101 op.addConstraint("h_d * xx_de <= u_e"); /* the capacity constraints (E constraints) */ 102 op.addConstraint("u_e <= U_max * z_e"); /* limit to maximum link capacity */ 103 104 if (topologyType.getString().equalsIgnoreCase("arbitrary-mesh")) 105 { 106 } 107 else if (topologyType.getString().equalsIgnoreCase("bidirectional-mesh")) 108 { 109 op.setInputParameter("Abid_ee", Abid_ee); 110 op.addConstraint("z_e == z_e * Abid_ee"); /* If a link exists, also the opposite */ 111 } 112 else if (topologyType.getString().equalsIgnoreCase("unidirectional-ring")) 113 { 114 op.setInputParameter("Aout_ne" , netPlan.getMatrixNodeLinkOutgoingIncidence()); 115 op.setInputParameter("Ain_ne" , netPlan.getMatrixNodeLinkIncomingIncidence()); 116 op.addConstraint("Aout_ne * z_e' == 1"); /* number of out links of a node is one */ 117 op.addConstraint("Ain_ne * z_e' == 1"); /* number of in links of a node is one */ 118 } 119 else if (topologyType.getString().equalsIgnoreCase("bidirectional-ring")) 120 { 121 op.setInputParameter("Aout_ne" , netPlan.getMatrixNodeLinkOutgoingIncidence()); 122 op.setInputParameter("Ain_ne" , netPlan.getMatrixNodeLinkIncomingIncidence()); 123 op.setInputParameter("Abid_ee", Abid_ee); 124 op.addConstraint("z_e == z_e * Abid_ee"); /* If a link exists, also teh opposite */ 125 op.addConstraint("Aout_ne * z_e' == 2"); /* number of out links of a node is two */ 126 op.addConstraint("Ain_ne * z_e' == 2"); /* number of in links of a node is two */ 127 } 128 else if (topologyType.getString().equalsIgnoreCase("bidirectional-tree")) 129 { 130 op.setInputParameter("Abid_ee", Abid_ee); 131 op.addConstraint("z_e == z_e * Abid_ee"); /* If a link exists, also teh opposite */ 132 op.addConstraint("sum(z_e) == " + (2*(N-1))); /* the number of links is characteristic of a tree */ 133 System.out.println ("num links: " + 2*(N-1)); 134 } 135 else throw new Net2PlanException ("Unknown topology type " + topologyType.getString()); 136 137 /* Call the solver to solve the problem */ 138 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 139 140 /* If no solution is found, quit */ 141 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 142 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 143 144 /* Retrieve the optimum solutions */ 145 final DoubleMatrix1D z_e = op.getPrimalSolution("z_e").view1D().copy (); 146 final DoubleMatrix1D u_e = op.getPrimalSolution("u_e").view1D().copy (); 147 final DoubleMatrix2D xx_de = op.getPrimalSolution("xx_de").view2D().copy (); 148 149 /* Sets the routing, capacities and links. Remove unused links (no capacity) */ 150 netPlan.setRoutingFromDemandLinkCarriedTraffic(xx_de , true , true , null); 151 netPlan.setVectorLinkCapacity(u_e); 152 netPlan.removeAllLinksUnused (PRECISION_FACTOR); 153 154 return "Ok! Num links: " + netPlan.getNumberOfLinks() + ", total capacity: " + u_e.zSum(); 155 } 156 157 @Override 158 public String getDescription() 159 { 160 return "This algorithm gives access to several variants of full topology design problems. Given a set of nodes and a set of unicast demands with known offered traffic. The algorithm searches for (i) the set of links to deploy, (ii) the link capacities, and (iii) how the traffic is routed over the links. The objective function consists in minimizing the cost, given by the sum of the link costs. The cost of a link is the sum of a fixed cost (proportional to the link length) that applies if the link exists (whatever its capacity is), and a variable cost proportional to its capacity and distance. Different problem variants can be selected, with different constraints (e.g. constraint the topology to be bidirectional, to be a ring, a tree...). The solution is searched by solving several variants of flow-link formulations."; 161 } 162 163 @Override 164 public List<Triple<String, String, String>> getParameters() 165 { 166 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 167 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 168 } 169}