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; 025import cern.jet.math.tdouble.DoubleFunctions; 026 027import com.jom.OptimizationProblem; 028import com.net2plan.interfaces.networkDesign.IAlgorithm; 029import com.net2plan.interfaces.networkDesign.Net2PlanException; 030import com.net2plan.interfaces.networkDesign.NetPlan; 031import com.net2plan.utils.InputParameter; 032import com.net2plan.utils.Triple; 033 034/** 035 * Solves several variants of node location problem formlations. 036 * @net2plan.description 037 * @net2plan.keywords Topology assignment (TA), JOM 038 * @net2plan.ocnbooksections Section 7.2 039 * @net2plan.inputParameters 040 * @author Pablo Pavon-Marino 041 */ 042public class Offline_tca_nodeLocation implements IAlgorithm 043{ 044 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"); 045 private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default."); 046 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)"); 047 private InputParameter linkCapacities = new InputParameter ("linkCapacities", (double) 100 , "The capacities to set in the links" , 0 , true , Double.MAX_VALUE , true); 048 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); 049 private InputParameter coreNodeCost = new InputParameter ("coreNodeCost", (double) 1 , "Cost of one core node. Link cost is proportional to its distance, and normalized to the cost of the longest possible link is one" , 0 , true , Double.MAX_VALUE , true); 050 private InputParameter K_max = new InputParameter ("K_max", (int) 5 , "Maximum number of access nodes that can be connected to a core node" , (int) 1 , Integer.MAX_VALUE); 051 private InputParameter maxNumCoreNodesPerSite = new InputParameter ("maxNumCoreNodesPerSite", (int) 1 , "Maximum number of core nodes that can be placed in a site." , (int) 1 , Integer.MAX_VALUE); 052 private InputParameter maxNumCoreNodes = new InputParameter ("maxNumCoreNodes", (int) -1 , "Maximum number of core nodes in the network. If <= 0, there is no limit."); 053 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 if (N == 0) throw new Net2PlanException("The input design must have nodes"); 064 065 final DoubleMatrix2D linkDistanceMatrix_nn = netPlan.getMatrixNode2NodeEuclideanDistance(); 066 final double maxDistance = linkDistanceMatrix_nn.getMaxLocation() [0]; 067 final DoubleMatrix2D c_ij = linkDistanceMatrix_nn.copy ().assign (DoubleFunctions.div(maxDistance)); // normalize so the maximum possible link cost is one 068 069 /* Create the optimization problem object (JOM library) */ 070 OptimizationProblem op = new OptimizationProblem(); 071 072 /* Set some input parameters */ 073 op.setInputParameter("c_ij", c_ij); 074 op.setInputParameter("K_max", K_max.getInt ()); 075 op.setInputParameter("C", coreNodeCost.getDouble()); 076 077 /* Add the decision variables to the problem */ 078 op.addDecisionVariable("z_j", true, new int[] { 1, N }, 0, maxNumCoreNodesPerSite.getInt()); /* 1 if there is a node in this site */ 079 op.addDecisionVariable("e_ij", true, new int[] { N, N }, 0, 1); /* 1 if site i is connected to site j */ 080 081 /* Sets the objective function */ 082 op.setObjectiveFunction("minimize", "C * sum(z_j) + sum (e_ij .* c_ij)"); 083 084 /* Constraints */ 085 op.addConstraint("sum(e_ij , 2) == 1"); /* each site is connected to a core site */ 086 op.addConstraint("sum(e_ij , 1) <= K_max * z_j"); /* a site is connected to other, if the second is a core site */ 087 if (maxNumCoreNodes.getInt() > 0) op.addConstraint("sum(z_j) <= " + maxNumCoreNodes.getInt()); /* limit to the total number of core nodes in the network */ 088 089 /* Call the solver to solve the problem */ 090 op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ()); 091 092 /* If no solution is found, quit */ 093 if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution"); 094 if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found"); 095 096 /* Retrieve the optimum solutions */ 097 DoubleMatrix1D z_j = op.getPrimalSolution("z_j").view1D(); 098 DoubleMatrix2D e_ij = op.getPrimalSolution("e_ij").view2D(); 099 100 System.out.println("z_j: " + z_j); 101 102 /* Remove all previous demands, links, protection segments, routes */ 103 netPlan.removeAllLinks(); 104 105 /* Save the new network links */ 106 for (int n = 0; n < N ; n ++) 107 if (z_j.get(n) == 1) netPlan.getNode (n).setAttribute("hasCoreNode" , "true"); else netPlan.getNode (n).setAttribute("hasCoreNode" , "false"); 108 for (int i = 0; i < N ; i ++) for (int j = 0; j < N ; j ++) 109 if (e_ij.get(i,j) == 1) 110 { 111 if (z_j.get(j) == 0) throw new RuntimeException ("Bad"); 112 if (i != j) netPlan.addLink(netPlan.getNode(i), netPlan.getNode(j), linkCapacities.getDouble(),linkDistanceMatrix_nn.get(i,j), linkPropagationSpeedInKmPerSecond.getDouble() , null); 113 } 114 115 return "Ok! Number of core nodes: " + z_j.zSum(); 116 } 117 118 @Override 119 public String getDescription() 120 { 121 return "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 (C) plus a cost per link, proportional to the link euclidean distance and normalized so that the maximum link cost is one. 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 an ILP and optimally solved using JOM."; 122 } 123 124 @Override 125 public List<Triple<String, String, String>> getParameters() 126 { 127 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 128 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 129 } 130 131 132}