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.DoubleFactory1D;
024import cern.colt.matrix.tdouble.DoubleMatrix1D;
025import cern.colt.matrix.tdouble.DoubleMatrix2D;
026import cern.jet.math.tdouble.DoubleFunctions;
027
028import com.jom.OptimizationProblem;
029import com.net2plan.interfaces.networkDesign.Configuration;
030import com.net2plan.interfaces.networkDesign.IAlgorithm;
031import com.net2plan.interfaces.networkDesign.Net2PlanException;
032import com.net2plan.interfaces.networkDesign.NetPlan;
033import com.net2plan.utils.Constants.RoutingType;
034import com.net2plan.utils.DoubleUtils;
035import com.net2plan.utils.InputParameter;
036import com.net2plan.utils.Triple;
037
038/**
039 * Solves several variants of unicast routing problems, with flow-path formulations
040 * @net2plan.description
041 * @net2plan.keywords JOM, Flow-path formulation, Flow assignment (FA)
042 * @net2plan.ocnbooksections Section 4.2, Section 4.6.3
043 * @net2plan.inputParameters 
044 * @author Pablo Pavon-Marino
045 */
046public class Offline_fa_xpFormulations implements IAlgorithm
047{
048        private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per demand" , 1 , Integer.MAX_VALUE);
049        private InputParameter shortestPathType = new InputParameter ("shortestPathType", "#select# hops km" , "Criteria to compute the shortest path. Valid values: 'hops' or 'km'");
050        private InputParameter nonBifurcatedRouting = new InputParameter ("nonBifurcatedRouting", false , "True if the routing is constrained to be non-bifurcated");
051        private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-av-num-hops minimax-link-utilization maximin-link-idle-capacity min-av-network-delay min-av-network-blocking" , "Type of optimization target. Choose among minimize the average number of hops, minimize the highest link utilization, maximize the lowest link idle capacity, minimize the average end-to-end network delay including queueing (M/M/1 estimation) and propagation delays, and minimize the average network blocking assuming independent Erlang-B blocking in each link, load sharing model");
052        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");
053        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");
054        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
055        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)");
056        private InputParameter binaryRatePerTrafficUnit_bps = new InputParameter ("binaryRatePerTrafficUnit_bps", (double) 1E6 , "Binary rate equivalent to one traffic unit (used only in average network delay minimization formulation)." , 0 , false , Double.MAX_VALUE , true);
057        private InputParameter averagePacketLengthInBytes = new InputParameter ("averagePacketLengthInBytes", (double) 500 , "Average packet length in bytes (used only in average network delay minimization formulation)." , 0 , false , Double.MAX_VALUE , true);
058        
059        @Override
060        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
061        {
062                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
063                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
064                if (solverName.getString ().equalsIgnoreCase("ipopt") && nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("With IPOPT solver, the routing cannot be constrained to be non-bifurcated");
065                
066                /* Initialize variables */
067                final int E = netPlan.getNumberOfLinks();
068                final int D = netPlan.getNumberOfDemands();
069                final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor"));
070                if (E == 0 || D == 0) throw new Net2PlanException("This algorithm requires a topology with links and a demand set");
071
072                /* Remove all unicast routed traffic. Any multicast routed traffic is kept */
073                netPlan.removeAllUnicastRoutingInformation();
074                netPlan.setRoutingType(RoutingType.SOURCE_ROUTING);
075
076                /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */
077                final DoubleMatrix1D linkCostVector = shortestPathType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm();
078
079                netPlan.addRoutesFromCandidatePathList(linkCostVector.toArray() , "K", Integer.toString(k.getInt ()), "maxLengthInKm", Double.toString(maxLengthInKm.getDouble () > 0? maxLengthInKm.getDouble () : Double.MAX_VALUE));
080                final int P = netPlan.getNumberOfRoutes(); 
081
082                /* Create the optimization problem object (JOM library) */
083                OptimizationProblem op = new OptimizationProblem();
084
085                /* Set some input parameters to the problem */
086                op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */
087                op.setInputParameter("A_dp", netPlan.getMatrixDemand2RouteAssignment()); /* 1 in position (d,p) if demand d is served by path p, 0 otherwise */ 
088                op.setInputParameter("A_ep", netPlan.getMatrixLink2RouteAssignment()); /* 1 in position (e,p) if link e is traversed by path p, 0 otherwise */
089                op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(), "row"); /* for each demand, its offered traffic */
090                op.setInputParameter("h_p", netPlan.getVectorRouteOfferedTrafficOfAssociatedDemand () , "row"); /* for each path, the offered traffic of its demand */
091
092                /* Write the problem formulations */
093                if (optimizationTarget.getString ().equals ("min-av-num-hops")) 
094                {
095                        op.setInputParameter("l_p", netPlan.getVectorRouteNumberOfLinks() , "row"); /* for each path, the number of traversed links */
096                        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 */
097
098                        op.setObjectiveFunction("minimize", "sum (l_p .* h_p .* xx_p)"); /* sum of the traffic in the links, proportional to the average number of hops  */
099                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
100                        op.addConstraint("A_ep * (h_p .* xx_p)' <= u_e'"); /* the traffic in each link cannot exceed its capacity  */
101                }
102                else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 
103                {
104                        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 */
105                        op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */
106                        op.setObjectiveFunction("minimize", "rho");
107                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
108                        op.addConstraint("A_ep * (h_p .* xx_p)' <= rho * u_e'"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization */
109                }
110                else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity"))
111                {
112                        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 */
113                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */
114                        op.setObjectiveFunction("maximize", "u");
115                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
116                        op.addConstraint("A_ep * (h_p .* xx_p)' <= -u + u_e'"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity */
117                }
118                else if (optimizationTarget.getString ().equals ("min-av-network-delay"))
119                {
120                        if (!solverName.getString ().equalsIgnoreCase("ipopt") || nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("This is a convex non linear model: please use IPOPT solver. The routing cannot be constrained to be non-bifurcated");
121                        op.setInputParameter("d_e_secs", netPlan.getVectorLinkPropagationDelayInMiliseconds().assign (DoubleFunctions.mult (0.001)) , "row");
122                        op.setInputParameter("L", averagePacketLengthInBytes.getDouble() * 8); /* average packet length in bits */
123                        op.setInputParameter("R", binaryRatePerTrafficUnit_bps.getDouble()); /* binary rate per traffic unit */
124                        op.addDecisionVariable("xx_p", false , new int[] { 1, P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p */
125                        op.addDecisionVariable("y_e", false, new int[] { 1, E }, DoubleUtils.zeros(E), netPlan.getVectorLinkCapacity().toArray()); /* traffic in the links (already limited to the link capacity) */
126                        op.setObjectiveFunction("minimize", "sum( y_e .* (d_e_secs + (L./R) * (1 ./ (u_e - y_e)))  )");
127                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
128                        op.addConstraint("A_ep * (h_p .* xx_p)' == y_e'"); /* sets y_e as the traffic in link e */
129                }
130                else if (optimizationTarget.getString ().equals ("min-av-network-blocking"))
131                {
132                        if (!solverName.getString ().equalsIgnoreCase("ipopt") || nonBifurcatedRouting.getBoolean()) throw new Net2PlanException ("This is a convex non linear model: please use IPOPT solver. The routing cannot be constrained to be non-bifurcated");
133                        op.addDecisionVariable("xx_p", false , new int[] { 1, P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p */
134                        op.addDecisionVariable("y_e", false, new int[] { 1, E }, DoubleUtils.zeros(E), netPlan.getVectorLinkCapacity().toArray()); /* traffic in the links (already limited to the link capacity) */
135                        op.setObjectiveFunction("minimize", "sum(y_e .* erlangB(y_e, u_e))");
136                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
137                        op.addConstraint("A_ep * (h_p .* xx_p)' == y_e'"); /* sets y_e as the traffic in link e */
138                }
139                else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
140
141                
142                System.out.println ("solverLibraryName: " +  solverLibraryName.getString ());
143                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
144                //op.solve(solverName.getString (), "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
145
146                System.out.println ("solverLibraryName: " +  solverLibraryName.getString ());
147
148                /* If no solution is found, quit */
149                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
150                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
151                
152                /* Save the solution found in the netPlan object */
153                final DoubleMatrix1D h_p = netPlan.getVectorRouteOfferedTrafficOfAssociatedDemand();
154                final DoubleMatrix1D xx_p = DoubleFactory1D.dense.make (op.getPrimalSolution("xx_p").to1DArray());
155                final DoubleMatrix1D x_p = xx_p.copy().assign (h_p , DoubleFunctions.mult);
156                netPlan.setVectorRouteCarriedTrafficAndOccupiedLinkCapacities(x_p , x_p);
157                netPlan.removeAllRoutesUnused(PRECISION_FACTOR); // routes with zero traffic (or close to zero, with PRECISION_FACTOR tolerance)
158
159                return "Ok!: The solution found is guaranteed to be optimal: " + op.solutionIsOptimal() + ". Number routes = " + netPlan.getNumberOfRoutes();
160        }
161
162        @Override
163        public String getDescription()
164        {
165                return "Given a network topology, the capacities in the links, and a set unicast traffic demands, this algorithm permits computing the optimum routing of the traffic (that is, the set of routes carrying the traffic of the demands) solving flow-path formulations, that start computing a set of admissible paths, and then solve the routing problem over them. Through a set of input parameters, the user can choose among different optimization targets and constraints.";
166        }
167
168        
169        @Override
170        public List<Triple<String, String, String>> getParameters()
171        {
172                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
173                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
174        }
175}