001/*******************************************************************************
002 * Copyright (c) 2017 Pablo Pavon Marino and others.
003 * All rights reserved. This program and the accompanying materials
004 * are made available under the terms of the 2-clause BSD License 
005 * which accompanies this distribution, and is available at
006 * https://opensource.org/licenses/BSD-2-Clause
007 *
008 * Contributors:
009 *     Pablo Pavon Marino and others - initial API and implementation
010 *******************************************************************************/
011
012
013
014
015 
016
017
018
019
020package com.net2plan.examples.ocnbook.offline;
021
022import cern.colt.matrix.tdouble.DoubleFactory1D;
023import cern.colt.matrix.tdouble.DoubleFactory2D;
024import cern.colt.matrix.tdouble.DoubleMatrix1D;
025import cern.colt.matrix.tdouble.DoubleMatrix2D;
026import cern.jet.math.tdouble.DoubleFunctions;
027import com.jom.OptimizationProblem;
028import com.net2plan.interfaces.networkDesign.Demand;
029import com.net2plan.interfaces.networkDesign.IAlgorithm;
030import com.net2plan.interfaces.networkDesign.Net2PlanException;
031import com.net2plan.interfaces.networkDesign.NetPlan;
032import com.net2plan.utils.Constants.RoutingType;
033import com.net2plan.utils.InputParameter;
034import com.net2plan.utils.Triple;
035
036import java.io.File;
037import java.util.ArrayList;
038import java.util.List;
039import java.util.Map;
040
041/**
042 * Solves a multihour routing problem with oblivious routing (common routing in all the time intervals) using a flow-path formulation
043 * @net2plan.description
044 * @net2plan.keywords Flow assignment (FA), Flow-path formulation, JOM, Multihour optimization
045 * @net2plan.ocnbooksections Section 4.6.8.1
046 * @net2plan.inputParameters 
047 * @author Pablo Pavon-Marino
048 */
049public class Offline_fa_xpMultihourObliviousRouting implements IAlgorithm
050{
051        private InputParameter rootOfNameOfInputTrafficFiles = new InputParameter ("rootOfNameOfInputTrafficFiles", "multiHourObliviousRouting", "Root of the names of the traffic files. If the root is \"XXX\", the files are XXX_tm0.n2p, XXX_tm1.n2p, ...");
052        private InputParameter rootOfNameOfOutputFiles = new InputParameter ("rootOfNameOfOutputFiles", "multiHourObliviousRouting", "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, ...");
053        private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per demand" , 1 , Integer.MAX_VALUE);
054        private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'");
055        private InputParameter nonBifurcatedRouting = new InputParameter ("nonBifurcatedRouting", false , "True if the routing is constrained to be non-bifurcated");
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 maxLengthInKm = new InputParameter ("maxLengthInKm", (double) 2000 , "Paths longer than this are considered not admissible. A non-positive number means this limit does not exist");
058        private InputParameter solverName = new InputParameter ("solverName", "#select# glpk ipopt xpress cplex", "The solver name to be used by JOM. GLPK and IPOPT are free, XPRESS and CPLEX commercial. GLPK, XPRESS 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");
059        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
060        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)");
061        
062        @Override
063        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
064        {
065                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
066                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
067                if (solverName.getString ().equalsIgnoreCase("ipopt") && nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("With IPOPT solver, the routing cannot be constrained to be non-bifurcated");
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.setRoutingTypeAllDemands(RoutingType.SOURCE_ROUTING);
080                netPlan.setTrafficMatrix(DoubleFactory2D.dense.make (N,N,1.0) , RoutingType.SOURCE_ROUTING); // 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                netPlan.addRoutesFromCandidatePathList(netPlan.computeUnicastCandidatePathList(linkCostVector , k.getInt(), maxLengthInKm.getDouble(), -1, -1, -1, -1, -1 , null));
085                final int P = netPlan.getNumberOfRoutes(); 
086
087                /* Create the netPlan files, one per interval */
088                ArrayList<NetPlan> netPlanFiles = new ArrayList<NetPlan> ();
089                while (true)
090                {
091                        try
092                        { 
093                                DoubleMatrix2D thisIntervalTrafficMatrix = new NetPlan(new File (rootOfNameOfInputTrafficFiles.getString() + "_tm" + netPlanFiles.size () + ".n2p")).getMatrixNode2NodeOfferedTraffic(); 
094                                NetPlan netPlanToAdd = netPlan.copy ();
095                                for (Demand d : netPlanToAdd.getDemands()) d.setOfferedTraffic(thisIntervalTrafficMatrix.get (d.getIngressNode().getIndex() , d.getEgressNode().getIndex()));
096                                netPlanFiles.add (netPlanToAdd);
097                        } catch (Exception e) {  break; }
098                }
099                final int T = netPlanFiles.size();
100                //System.out.println ("Number of traffic matrices loaded: " + netPlanFiles.size ());
101
102                /* Create the optimization problem object (JOM library) */
103                OptimizationProblem op = new OptimizationProblem();
104
105                /* Set some input parameters to the problem */
106                op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */
107                op.setInputParameter("A_dp", netPlan.getMatrixDemand2RouteAssignment()); /* 1 in position (d,p) if demand d is served by path p, 0 otherwise */ 
108                op.setInputParameter("A_ep", netPlan.getMatrixLink2RouteAssignment()); /* 1 in position (e,p) if link e is traversed by path p, 0 otherwise */
109                DoubleMatrix2D h_dt = DoubleFactory2D.dense.make (N*(N-1),T);
110                DoubleMatrix2D h_pt = DoubleFactory2D.dense.make (P,T);
111                for (int t = 0; t < T ; t ++) 
112                { 
113                        h_dt.viewColumn(t).assign (netPlanFiles.get(t).getVectorDemandOfferedTraffic());
114                        h_pt.viewColumn(t).assign (netPlanFiles.get(t).getVectorRouteOfferedTrafficOfAssociatedDemand());
115                }
116                op.setInputParameter("h_dt", h_dt); /* for each demand and time interval , its offered traffic */
117                op.setInputParameter("h_pt", h_pt); /* for each path and time interval , the offered traffic of its demand */
118                op.setInputParameter("onesT", DoubleFactory1D.dense.make (T,1.0) , "row"); /* a vector of ones of size T */
119
120                /* Write the problem formulations */
121                if (optimizationTarget.getString ().equals ("min-av-num-hops")) 
122                {
123                        op.setInputParameter("l_p", netPlan.getVectorRouteNumberOfLinks() , "row"); /* for each path, the number of traversed links */
124                        op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean() , new int[] { 1 , P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p (the same in all time intervals)  */
125                        op.setObjectiveFunction("minimize", "sum (diag (l_p .* xx_p) * h_pt)"); /* sum of the traffic in the links in all the time intervals, proportional to the average number of hops  */
126                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
127                        op.addConstraint("A_ep * (diag (xx_p) * h_pt) <= u_e' * onesT"); /* the traffic in each link cannot exceed its capacity in any time slot */
128                }
129                else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 
130                {
131                        op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean() , new int[] { 1 , P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p (the same in all time intervals)  */
132                        op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */
133                        op.setObjectiveFunction("minimize", "rho");
134                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
135                        op.addConstraint("A_ep * (diag (xx_p) * 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 */
136                }
137                else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity"))
138                {
139                        op.addDecisionVariable("xx_p", nonBifurcatedRouting.getBoolean() , new int[] { 1 , P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p (the same in all time intervals)  */
140                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */
141                        op.setObjectiveFunction("maximize", "u");
142                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
143                        op.addConstraint("A_ep * (diag (xx_p) * 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 */
144                }
145                else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
146
147                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
148
149                /* If no solution is found, quit */
150                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
151                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
152                
153                /* Save the solution found in the netPlan object */
154                final DoubleMatrix1D xx_p = DoubleFactory1D.sparse.make (op.getPrimalSolution("xx_p").to1DArray());
155                for (int t = 0 ; t < T ; t ++)
156                {
157                        NetPlan thisNp = netPlanFiles.get(t);
158                        final DoubleMatrix1D h_p = thisNp.getVectorRouteOfferedTrafficOfAssociatedDemand();
159                        final DoubleMatrix1D x_p = xx_p.copy().assign (h_p , DoubleFunctions.mult);
160                        thisNp.setVectorRouteCarriedTrafficAndOccupiedLinkCapacities(x_p , x_p);
161                        thisNp.removeAllRoutesUnused(PRECISION_FACTOR); // routes with zero traffic (or close to zero, with PRECISION_FACTOR tolerance)
162                        thisNp.saveToFile(new File (rootOfNameOfOutputFiles.getString() + "_res_tm" + netPlanFiles.size () + ".n2p"));
163                        if (t == 0) netPlan.assignFrom (thisNp);
164                        if (!thisNp.getLinksOversubscribed().isEmpty()) throw new RuntimeException ("Bad");
165                        if (thisNp.getVectorDemandBlockedTraffic().zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + thisNp.getVectorDemandBlockedTraffic().zSum());
166                }
167
168                return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal() + ". Number routes = " + netPlan.getNumberOfRoutes();
169        }
170
171        @Override
172        public String getDescription()
173        {
174                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 oblivious routing (common routing to all the time intervals) that optimizes the selected optimization target.";
175        }
176
177        
178        @Override
179        public List<Triple<String, String, String>> getParameters()
180        {
181                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
182                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
183        }
184}