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}