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