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.io.File;
021import java.util.ArrayList;
022import java.util.List;
023import java.util.Map;
024
025import cern.colt.matrix.tdouble.DoubleFactory1D;
026import cern.colt.matrix.tdouble.DoubleFactory2D;
027import cern.colt.matrix.tdouble.DoubleMatrix1D;
028import cern.colt.matrix.tdouble.DoubleMatrix2D;
029import cern.colt.matrix.tdouble.DoubleMatrix3D;
030import cern.jet.math.tdouble.DoubleFunctions;
031
032import com.jom.DoubleMatrixND;
033import com.jom.OptimizationProblem;
034import com.net2plan.interfaces.networkDesign.Configuration;
035import com.net2plan.interfaces.networkDesign.Demand;
036import com.net2plan.interfaces.networkDesign.IAlgorithm;
037import com.net2plan.interfaces.networkDesign.Link;
038import com.net2plan.interfaces.networkDesign.Net2PlanException;
039import com.net2plan.interfaces.networkDesign.NetPlan;
040import com.net2plan.utils.Constants.RoutingType;
041import com.net2plan.utils.InputParameter;
042import com.net2plan.utils.StringUtils;
043import com.net2plan.utils.Triple;
044
045/**
046 * Finds the multiperiod (e.g. subsequent years) routing and capacity acquisitions with a MILP formulation
047 * @net2plan.description
048 * @net2plan.keywords Capacity assignment (CA), Modular capacities, Flow assignment (FA), Multiperiod optimization, JOM
049 * @net2plan.ocnbooksections Section 5.2.3
050 * @net2plan.inputParameters 
051 * @author Pablo Pavon-Marino
052 */
053public class Offline_cfa_xpMultiperiodModularCapacities implements IAlgorithm
054{
055        private InputParameter rootOfNameOfInputTrafficFiles = new InputParameter ("rootOfNameOfInputTrafficFiles", "multiPeriodModularCapacities", "Root of the names of the traffic files. If the root is \"XXX\", the files are XXX_tm0.n2p, XXX_tm1.n2p, ...");
056        private InputParameter rootOfNameOfOutputFiles = new InputParameter ("rootOfNameOfOutputFiles", "multiPeriodModularCapacities", "Root of the names of the output files. One per input traffic file. If the root is \"XXX\", the files are XXX_res_tm0.n2p, XXX_res_tm1.n2p, ...");
057        private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per demand" , 1 , Integer.MAX_VALUE);
058        private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'");
059        private InputParameter nonBifurcatedRouting = new InputParameter ("nonBifurcatedRouting", false , "True if the routing is constrained to be non-bifurcated");
060        private InputParameter maxLengthInKm = new InputParameter ("maxLengthInKm", (double) 2000 , "Paths longer than this are considered not admissible. A non-positive number means this limit does not exist");
061        private InputParameter solverName = new InputParameter ("solverName", "#select# glpk cplex", "The solver name to be used by JOM. GLPK is free, CPLEX commercial. Both GLPK and CPLEX solve linear problems w/w.o integer contraints.");
062        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
063        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)");
064        private InputParameter costPerCapacityModuleType = new InputParameter ("costPerCapacityModuleType", "1 3 6", "The cost of each module of the given type");
065        private InputParameter capacityOfEachCapacityModuleType = new InputParameter ("capacityOfEachCapacityModuleType", "10 40 100", "The capacity of each module of the given type");
066        private InputParameter costReductionFactor = new InputParameter ("costReductionFactor", (double) 1 , "The cost of each element at period t is the cost at the previous period multiplied by this. Typically below one since things tend to decrease its price because of improvement in manufacturing" , 0 , true , Double.MAX_VALUE , true);
067
068        @Override
069        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
070        {
071                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
072                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
073                if (!shortestPathType.getString().equalsIgnoreCase("km") && !shortestPathType.getString().equalsIgnoreCase("hops"))
074                        throw new Net2PlanException("Wrong shortestPathType parameter");
075                final DoubleMatrix1D u_k = DoubleFactory1D.dense.make (StringUtils.toDoubleArray(StringUtils.split(capacityOfEachCapacityModuleType.getString())));
076                final DoubleMatrix1D c_k0 = DoubleFactory1D.dense.make (StringUtils.toDoubleArray(StringUtils.split(costPerCapacityModuleType.getString())));
077                final int K = (int) u_k.size (); // number of types of capacity modules 
078                if (K == 0) throw new Net2PlanException ("No capacity modules defined");
079                if (c_k0.size() != K) throw new Net2PlanException ("The number of costs should be equal to the number of types of capacity modules");
080                if (u_k.getMinLocation() [0] < 0) throw new Net2PlanException ("Capacities of the modules cannot be negative");
081                if (c_k0.getMinLocation() [0] < 0) throw new Net2PlanException ("Costs of the modules cannot be negative");
082                
083                /* Initialize variables */
084                final int N = netPlan.getNumberOfNodes ();
085                final int E = netPlan.getNumberOfLinks ();
086                final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor"));
087                if (E == 0) throw new Net2PlanException("This algorithm requires a topology with links");
088
089                /* Remove all unicast routed traffic. Any multicast routed traffic is kept */
090                netPlan.removeAllUnicastRoutingInformation();
091                netPlan.setRoutingType(RoutingType.SOURCE_ROUTING);
092                netPlan.setTrafficMatrix(DoubleFactory2D.dense.make (N,N,1.0)); // just to create the demands
093
094                /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */
095                final DoubleMatrix1D linkCostVectorForCandidatePathList = shortestPathType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm();
096                
097                netPlan.addRoutesFromCandidatePathList(linkCostVectorForCandidatePathList.toArray() , "K", Integer.toString(k.getInt ()), "maxLengthInKm", Double.toString(maxLengthInKm.getDouble () > 0? maxLengthInKm.getDouble () : Double.MAX_VALUE));
098                final int P = netPlan.getNumberOfRoutes(); 
099                
100                /* Create the netPlan files, one per interval */
101                ArrayList<NetPlan> netPlanFiles = new ArrayList<NetPlan> ();
102                while (true)
103                {
104                        try
105                        { 
106                                DoubleMatrix2D thisIntervalTrafficMatrix = new NetPlan(new File (rootOfNameOfInputTrafficFiles.getString() + "_tm" + netPlanFiles.size () + ".n2p")).getMatrixNode2NodeOfferedTraffic(); 
107                                if (thisIntervalTrafficMatrix.rows () != N) throw new Net2PlanException ("The number of nodes in traffic matrix: " + rootOfNameOfInputTrafficFiles.getString() + "_tm" + netPlanFiles.size () + ".n2p (" + thisIntervalTrafficMatrix.rows() + ") is not correct (" + N + ")");
108                                NetPlan netPlanToAdd = netPlan.copy ();
109                                for (Demand d : netPlanToAdd.getDemands()) d.setOfferedTraffic(thisIntervalTrafficMatrix.get (d.getIngressNode().getIndex() , d.getEgressNode().getIndex()));
110                                netPlanFiles.add (netPlanToAdd);
111                        } catch (Exception e) { e.printStackTrace();  break; }
112                }
113                final int T = netPlanFiles.size();
114
115                /* Compute the costs */
116                final DoubleMatrix2D c_kt = DoubleFactory2D.dense.make (K,T);
117                c_kt.viewColumn(0).assign (c_k0);
118                for (int t = 1 ; t < T ; t ++)
119                        c_kt.viewColumn(t).assign (c_kt.viewColumn (t-1).copy ()).assign(DoubleFunctions.mult(costReductionFactor.getDouble()));
120
121                /* Create the optimization problem object (JOM library) */
122                OptimizationProblem op = new OptimizationProblem();
123
124                /* Set some input parameters to the problem */
125                op.setInputParameter("A_dp", netPlan.getMatrixDemand2RouteAssignment()); /* 1 in position (d,p) if demand d is served by path p, 0 otherwise */ 
126                op.setInputParameter("A_ep", netPlan.getMatrixLink2RouteAssignment()); /* 1 in position (e,p) if link e is traversed by path p, 0 otherwise */
127                DoubleMatrix2D h_dt = DoubleFactory2D.dense.make (N*(N-1),T);
128                DoubleMatrix2D h_pt = DoubleFactory2D.dense.make (P,T);
129                for (int t = 0; t < T ; t ++) 
130                { 
131                        h_dt.viewColumn(t).assign (netPlanFiles.get(t).getVectorDemandOfferedTraffic());
132                        h_pt.viewColumn(t).assign (netPlanFiles.get(t).getVectorRouteOfferedTrafficOfAssociatedDemand());
133                }
134                op.setInputParameter("h_dt", h_dt); /* for each demand and time interval , its offered traffic */
135                op.setInputParameter("h_pt", h_pt); /* for each path and time interval , the offered traffic of its demand */
136                op.setInputParameter("u_k", u_k , "row"); /* The capacity of each module of type k */
137                op.setInputParameter("c_kt", c_kt); /* The cost of a module of type k, acquired to be used starting in interval t */
138                op.setInputParameter("onesT", DoubleFactory1D.dense.make (T,1.0) , "row"); /* a vector of ones of size T */
139                DoubleMatrix2D timeAccumulationMatrix = DoubleFactory2D.dense.make (T,T); for (int t1 = 0 ; t1 < T; t1 ++) for (int t2 = t1 ; t2 < T ; t2++) timeAccumulationMatrix.set(t1,t2,1.0); 
140                op.setInputParameter("T_tt", timeAccumulationMatrix); /* 1 if column >= row: if the time of acquisition (row) is equal or higher than the time if observation (t2) */
141
142                op.addDecisionVariable("xx_pt", nonBifurcatedRouting.getBoolean() , new int[] { P , T }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p in each time interval  */
143                op.addDecisionVariable("a_ket", true , new int[] { K , E , T }, 0, 1); /* the number of elements of type k, acquired at time t, and placed at link e (in t and all intervals after t) */
144                
145                op.setObjectiveFunction("minimize", "sum (c_kt .* sum(a_ket,2)) "); /* sum of the cost of all the elements acquired, at the moment of acquisition */
146                op.addConstraint("A_dp * xx_pt == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) in any time period */
147                op.addConstraint("A_ep * (xx_pt .* h_pt) <= sum(u_k * a_ket,1) * T_tt"); /* the traffic in each link cannot exceed its capacity in any time period */
148
149                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
150
151                /* If no solution is found, quit */
152                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
153                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
154                
155                /* Save the solution found in the netPlan object */
156                final DoubleMatrix2D xx_pt = op.getPrimalSolution("xx_pt").view2D ();
157                final DoubleMatrix3D a_ket = op.getPrimalSolution("a_ket").view3D("sparse");
158                
159                for (int t = 0 ; t < T ; t ++)
160                {
161                        NetPlan thisNp = netPlanFiles.get(t);
162                        final DoubleMatrix1D h_p = thisNp.getVectorRouteOfferedTrafficOfAssociatedDemand();
163                        final DoubleMatrix1D x_p = xx_pt.viewColumn(t).copy().assign (h_p , DoubleFunctions.mult);
164                        System.out.println ("h_p: " + h_p);
165                        thisNp.setVectorRouteCarriedTrafficAndOccupiedLinkCapacities(x_p , x_p);
166                        for (Link link : thisNp.getLinks ())
167                        {
168                                final int e = link.getIndex ();
169                                double linkCapacityAccumulatingPreviosModules = 0; for (int t1 = 0; t1 <= t ; t1 ++) for (int k = 0 ; k < K ; k ++) linkCapacityAccumulatingPreviosModules += u_k.get(k) * a_ket.get(k,e,t1);
170                                link.setCapacity(linkCapacityAccumulatingPreviosModules);
171                                for (int k = 0 ; k < K ; k ++) link.setAttribute ("numNewModulesType_" + k , "" + a_ket.get (k,e,t));
172                        }
173                        thisNp.removeAllRoutesUnused(PRECISION_FACTOR); // routes with zero traffic (or close to zero, with PRECISION_FACTOR tolerance)
174                        thisNp.saveToFile(new File (rootOfNameOfOutputFiles.getString() + "_res_tm" + netPlanFiles.size () + ".n2p"));
175                        if (t == 0) netPlan.assignFrom (thisNp);
176                        if (thisNp.getVectorLinkOversubscribedTraffic().zSum () > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + thisNp.getVectorLinkOversubscribedTraffic().zSum ());
177                        if (thisNp.getDemandTotalBlockedTraffic() > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + thisNp.getDemandTotalBlockedTraffic());
178                }
179
180                return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal() + ". Total cost = " + op.parseExpression("sum (c_kt .* sum(a_ket,2))").evaluate("a_ket" , new DoubleMatrixND (a_ket));
181        }
182
183        @Override
184        public String getDescription()
185        {
186                return "Given a network with a set of given nodes, and links, and a given a sequence of offered traffic matrices in the network, corresponding to the (typically increasing) traffic of successive periods (e.g. each for one year). The link capacities are constrained to be modular: selectable among a set of user-defined capacity modules. Each capacity module type is characterized by its capacity and its cost. We assume that the costs of the capacity modules decrease along time, according to a cost reduction factor. Then, the algorithm should find for each of the successive periods: (i) the routing of the traffic in each period, (ii) how many NEW modules of capacity are installed in each link. Once a capacity module is installed in a link, we assume that it is never moved. The optimization target is minimizing the total cost along all the periods. This algorithm optimizes the problem solving a flow-path formulation using JOM.";
187        }
188
189        
190        @Override
191        public List<Triple<String, String, String>> getParameters()
192        {
193                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
194                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
195        }
196}