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
018
019package com.net2plan.examples.ocnbook.offline;
020
021import java.io.File;
022import java.util.ArrayList;
023import java.util.List;
024import java.util.Map;
025
026import cern.colt.matrix.tdouble.DoubleFactory1D;
027import cern.colt.matrix.tdouble.DoubleFactory2D;
028import cern.colt.matrix.tdouble.DoubleMatrix1D;
029import cern.colt.matrix.tdouble.DoubleMatrix2D;
030import cern.jet.math.tdouble.DoubleFunctions;
031
032import com.jom.OptimizationProblem;
033import com.net2plan.interfaces.networkDesign.Configuration;
034import com.net2plan.interfaces.networkDesign.Demand;
035import com.net2plan.interfaces.networkDesign.IAlgorithm;
036import com.net2plan.interfaces.networkDesign.Net2PlanException;
037import com.net2plan.interfaces.networkDesign.NetPlan;
038import com.net2plan.utils.Constants.RoutingType;
039import com.net2plan.utils.InputParameter;
040import com.net2plan.utils.Triple;
041
042/**
043 * Solves a multihour routing problem with dynamic routing (routing may be different at different time intervals) using a flow-path formulation
044 * @net2plan.description
045 * @net2plan.keywords Flow assignment (FA), Flow-path formulation, JOM, Multihour optimization
046 * @net2plan.ocnbooksections Section 4.6.8.2
047 * @net2plan.inputParameters 
048 * @author Pablo Pavon-Marino
049 */
050public class Offline_fa_xpMultihourDynamicRouting implements IAlgorithm
051{
052        private InputParameter rootOfNameOfInputTrafficFiles = new InputParameter ("rootOfNameOfInputTrafficFiles", "multiHourDynamicRouting", "Root of the names of the traffic files. If the root is \"XXX\", the files are XXX_tm0.n2p, XXX_tm1.n2p, ...");
053        private InputParameter rootOfNameOfOutputFiles = new InputParameter ("rootOfNameOfOutputFiles", "multiHourDynamicRouting", "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, ...");
054        private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per demand" , 1 , Integer.MAX_VALUE);
055        private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'");
056        private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-av-num-hops minimax-link-utilization maximin-link-idle-capacity" , "Type of optimization target. Choose among minimize the average number of hops, minimize the highest link utilization, maximize the lowest link idle capacity");
057        private InputParameter gammaFactor = new InputParameter ("gammaFactor", (double) 1e-5 , "Penalization factor to changing the routing of traffic");
058        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");
059        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");
060        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
061        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)");
062        
063        @Override
064        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
065        {
066                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
067                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
068                if (!shortestPathType.getString().equalsIgnoreCase("km") && !shortestPathType.getString().equalsIgnoreCase("hops"))
069                        throw new Net2PlanException("Wrong shortestPathType parameter");
070                
071                /* Initialize variables */
072                final int N = netPlan.getNumberOfNodes ();
073                final int E = netPlan.getNumberOfLinks ();
074                final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor"));
075                if (E == 0) throw new Net2PlanException("This algorithm requires a topology with links");
076
077                /* Remove all unicast routed traffic. Any multicast routed traffic is kept */
078                netPlan.removeAllUnicastRoutingInformation();
079                netPlan.setRoutingType(RoutingType.SOURCE_ROUTING);
080                netPlan.setTrafficMatrix(DoubleFactory2D.dense.make (N,N,1.0)); // just to create the demands
081
082                /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */
083                final DoubleMatrix1D linkCostVector = shortestPathType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm();
084
085                netPlan.addRoutesFromCandidatePathList(linkCostVector.toArray() , "K", Integer.toString(k.getInt ()), "maxLengthInKm", Double.toString(maxLengthInKm.getDouble () > 0? maxLengthInKm.getDouble () : Double.MAX_VALUE));
086                final int P = netPlan.getNumberOfRoutes(); 
087                
088                /* Create the netPlan files, one per interval */
089                ArrayList<NetPlan> netPlanFiles = new ArrayList<NetPlan> ();
090                while (true)
091                {
092                        try
093                        { 
094                                DoubleMatrix2D thisIntervalTrafficMatrix = new NetPlan(new File (rootOfNameOfInputTrafficFiles.getString() + "_tm" + netPlanFiles.size () + ".n2p")).getMatrixNode2NodeOfferedTraffic(); 
095                                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 + ")");
096                                NetPlan netPlanToAdd = netPlan.copy ();
097                                for (Demand d : netPlanToAdd.getDemands()) d.setOfferedTraffic(thisIntervalTrafficMatrix.get (d.getIngressNode().getIndex() , d.getEgressNode().getIndex()));
098                                netPlanFiles.add (netPlanToAdd);
099                        } catch (Exception e) { e.printStackTrace();  break; }
100                }
101                final int T = netPlanFiles.size();
102
103
104                /* Create the optimization problem object (JOM library) */
105                OptimizationProblem op = new OptimizationProblem();
106
107                /* Set some input parameters to the problem */
108                op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */
109                op.setInputParameter("A_dp", netPlan.getMatrixDemand2RouteAssignment()); /* 1 in position (d,p) if demand d is served by path p, 0 otherwise */ 
110                op.setInputParameter("A_ep", netPlan.getMatrixLink2RouteAssignment()); /* 1 in position (e,p) if link e is traversed by path p, 0 otherwise */
111                DoubleMatrix2D h_dt = DoubleFactory2D.dense.make (N*(N-1),T);
112                DoubleMatrix2D h_pt = DoubleFactory2D.dense.make (P,T);
113                DoubleMatrix2D P_ttminus1 = DoubleFactory2D.dense.make (T,T);
114                for (int t = 0; t < T ; t ++) 
115                { 
116                        h_dt.viewColumn(t).assign (netPlanFiles.get(t).getVectorDemandOfferedTraffic());
117                        h_pt.viewColumn(t).assign (netPlanFiles.get(t).getVectorRouteOfferedTrafficOfAssociatedDemand());
118                        P_ttminus1.set(t,t,1.0); P_ttminus1.set(t,(t-1+T)%T,-1.0);
119                }
120                op.setInputParameter("h_dt", h_dt); /* for each demand and time interval , its offered traffic */
121                op.setInputParameter("h_pt", h_pt); /* for each path and time interval , the offered traffic of its demand */
122                op.setInputParameter("P_ttminus1", P_ttminus1); /* Each column t has a one in t and a mins one in t-1. Used to compute xx_pt - xx_p{t-1) easily as matrix multiplication */
123                op.setInputParameter("gamma", gammaFactor.getDouble() / Math.pow (h_dt.zSum() , 2)); /* Gamma factor is normalized dividing by the maximum traffic that can be moved in all time slots, to the square. Then, gamma becomes the maximum value that the penalization summatory can take */
124                op.setInputParameter("onesT", DoubleFactory1D.dense.make (T,1.0) , "row"); /* a vector of ones of size T */
125
126                /* Write the problem formulations */
127                if (optimizationTarget.getString ().equals ("min-av-num-hops")) 
128                {
129                        op.setInputParameter("l_p", netPlan.getVectorRouteNumberOfLinks() , "row"); /* for each path, the number of traversed links */
130                        op.addDecisionVariable("xx_pt", false , new int[] { P , T }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p in each time interval  */
131                        if (gammaFactor.getDouble() == 0)
132                                op.setObjectiveFunction("minimize", "sum (diag (l_p) * xx_pt .* h_pt)"); /* sum of the traffic in the links in all the time intervals, proportional to the average number of hops  */
133                        else
134                                op.setObjectiveFunction("minimize", "sum (diag (l_p) * xx_pt .* h_pt) + gamma * sum ((h_pt .* (xx_pt*P_ttminus1)) ^ 2)"); /* sum of the traffic in the links in all the time intervals, proportional to the average number of hops  */
135                        op.addConstraint("A_dp * xx_pt == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) in any time interval */
136                        op.addConstraint("A_ep * (xx_pt .* h_pt) <= u_e' * onesT"); /* the traffic in each link cannot exceed its capacity in any time slot */
137                }
138                else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 
139                {
140                        op.addDecisionVariable("xx_pt", false , new int[] { P , T }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p in each time interval  */
141                        op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization in all time slots */
142                        if (gammaFactor.getDouble() == 0)
143                                op.setObjectiveFunction("minimize", "rho");
144                        else
145                                op.setObjectiveFunction("minimize", "rho + gamma * sum ((h_pt .* (xx_pt*P_ttminus1)) ^ 2)");
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 interval */
147                        op.addConstraint("A_ep * (xx_pt .* h_pt) <= rho * u_e' * onesT"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization in any time slot */
148                }
149                else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity"))
150                {
151                        op.addDecisionVariable("xx_pt", false , new int[] { P , T }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p in each time interval  */
152                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity in all time slots */
153                        if (gammaFactor.getDouble() == 0)
154                                op.setObjectiveFunction("maximize", "u");
155                        else
156                                op.setObjectiveFunction("maximize", "u - gamma * sum ((h_pt .* (xx_pt*P_ttminus1)) ^ 2)");
157                        op.addConstraint("A_dp * xx_pt == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) in any time interval */
158                        op.addConstraint("A_ep * (xx_pt .* h_pt) <= -u + u_e' * onesT"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity in all time intervals */
159                }
160                else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
161
162                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
163
164                /* If no solution is found, quit */
165                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
166                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
167                
168                /* Save the solution found in the netPlan object */
169                final DoubleMatrix2D xx_pt = op.getPrimalSolution("xx_pt").view2D ();
170                for (int t = 0 ; t < T ; t ++)
171                {
172                        NetPlan thisNp = netPlanFiles.get(t);
173                        final DoubleMatrix1D h_p = thisNp.getVectorRouteOfferedTrafficOfAssociatedDemand();
174                        final DoubleMatrix1D x_p = xx_pt.viewColumn(t).copy().assign (h_p , DoubleFunctions.mult);
175                        thisNp.setVectorRouteCarriedTrafficAndOccupiedLinkCapacities(x_p , x_p);
176                        thisNp.removeAllRoutesUnused(PRECISION_FACTOR); // routes with zero traffic (or close to zero, with PRECISION_FACTOR tolerance)
177                        thisNp.saveToFile(new File (rootOfNameOfOutputFiles.getString() + "_res_tm" + netPlanFiles.size () + ".n2p"));
178                        if (t == 0) netPlan.assignFrom (thisNp);
179                        if (thisNp.getVectorLinkOversubscribedTraffic().zSum () > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + thisNp.getVectorLinkOversubscribedTraffic().zSum ());
180                        if (thisNp.getDemandTotalBlockedTraffic() > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + thisNp.getDemandTotalBlockedTraffic());
181                }
182
183                DoubleMatrix2D reroutedTraffic_pt = xx_pt.zMult (P_ttminus1 , null).assign (h_pt,  DoubleFunctions.mult).assign (DoubleFunctions.abs);
184
185                return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal() + ". Sum rerouted traffic all time slots = " + reroutedTraffic_pt.zSum();
186        }
187
188        @Override
189        public String getDescription()
190        {
191                return "Given a set of traffic matrices, corresponding to the offered network traffic at different times of the day, this algorithm solves a flow-path formulation for finding the set of routings (one per time interval) that optimizes the selected optimization target. The objective function includes a penalization factor to avoid excessive reroutings along the day."; 
192        }
193
194        
195        @Override
196        public List<Triple<String, String, String>> getParameters()
197        {
198                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
199                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
200        }
201}