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.jet.math.tdouble.DoubleFunctions;
026
027import com.jom.OptimizationProblem;
028import com.net2plan.interfaces.networkDesign.Configuration;
029import com.net2plan.interfaces.networkDesign.IAlgorithm;
030import com.net2plan.interfaces.networkDesign.Net2PlanException;
031import com.net2plan.interfaces.networkDesign.NetPlan;
032import com.net2plan.utils.DoubleUtils;
033import com.net2plan.utils.InputParameter;
034import com.net2plan.utils.Triple;
035
036/**
037 * Solves several variants of multicast routing problems, with flow-path formulations
038 * @net2plan.description
039 * @net2plan.keywords Multicast, JOM, Flow-path formulation, Flow assignment (FA)
040 * @net2plan.ocnbooksections Section 4.6.2
041 * @net2plan.inputParameters 
042 * @author Pablo Pavon-Marino
043 */
044public class Offline_fa_xpFormulationsMulticast implements IAlgorithm
045{
046        private InputParameter linkCostType = new InputParameter ("linkCostType", "#select# hops km" , "Criteria to compute the multicast tree cost. Valid values: 'hops' (all links cost one) or 'km' (link cost is its length in km)");
047        private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-consumed-bandwidth min-av-num-hops minimax-link-utilization maximin-link-idle-capacity min-av-network-blocking" , "Type of optimization target. Choose among minimize the total traffic in the links, minimize the average number of hops from ingress to different egress nodes, minimize the highest link utilization, maximize the lowest link idle capacity, and minimize the average network blocking assuming independent Erlang-B blocking in each link, load sharing model");
048        private InputParameter nonBifurcatedRouting = new InputParameter ("nonBifurcatedRouting", false , "True if the routing is constrained to be non-bifurcated");
049        private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible multicast trees per demand" , 1 , Integer.MAX_VALUE);
050        private InputParameter maxCopyCapability = new InputParameter ("maxCopyCapability", (int) -1 , "Maximum number of copies of the traffic a node can make (this is the maximum number of output links in a node of the same multicast tree). A non-positive value means no limit");
051        private InputParameter maxE2ELengthInKm = new InputParameter ("maxLengthInKm", (double) -1 , "The path from an origin to any destination in any multicast tree cannot be longer than this. A non-positive number means this limit does not exist");
052        private InputParameter maxE2ENumHops = new InputParameter ("maxE2ENumHops", (int) -1 , "The path from an origin to any destination in any multicast tree cannot have more than this number of hops. A non-positive number means this limit does not exist");
053        private InputParameter maxE2EPropDelayInMs = new InputParameter ("maxE2EPropDelayInMs", (double) -1 , "The path from an origin to any destination in any multicast tree cannot have more than this propagation delay in miliseconds. A non-positive number means this limit does not exist");
054        private InputParameter maxTreeCost = new InputParameter ("maxTreeCost", (double) -1 , "The trees with a cost (measured as stated by linkCostType) are considered not admissible. A non-positive number means this limit does not exist");
055        private InputParameter maxTreeCostFactorRespectToMinimumCostTree = new InputParameter ("maxTreeCostFactorRespectToMinimumCostTree", (double) -1 , "The trees with a cost (measured as stated by linkCostType) higher than this factor multiplied by the cost of the minimum cost multicast tree for that demand, are considered not admissible. A non-positive number means this limit does not exist");
056        private InputParameter maxTreeCostRespectToMinimumCostTree = new InputParameter ("maxTreeCostRespectToMinimumCostTree", (double) -1 , "The trees with a cost (measured as stated by linkCostType) higher than this parameter plus the cost of the minimum cost multicast tree for that demand, are considered not admissible. A non-positive number means this limit does not exist");
057        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");
058        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
059        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)");
060        
061        @Override
062        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
063        {
064                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
065                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
066                if (!linkCostType.getString().equalsIgnoreCase("km") && !linkCostType.getString().equalsIgnoreCase("hops"))
067                        throw new Net2PlanException("Wrong linkCostType parameter");
068                
069                /* Initialize variables */
070                final int E = netPlan.getNumberOfLinks();
071                final int MD = netPlan.getNumberOfMulticastDemands();
072                final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor"));
073                if (E == 0 || MD == 0) throw new Net2PlanException("This algorithm requires a topology with links and a multicast demand set");
074
075                /* Remove all multicast routed traffic. Any unicast routed traffic is kept */
076                netPlan.removeAllMulticastTrees();
077
078                /* Add all the k-shortest candidate routes to the netPlan object carrying no traffic */
079                final DoubleMatrix1D linkCostVector = linkCostType.getString().equalsIgnoreCase("hops")? DoubleFactory1D.dense.make (E , 1.0) : netPlan.getVectorLinkLengthInKm();
080
081                netPlan.addMulticastTreesFromCandidateTreeList(netPlan.computeMulticastCandidatePathList(linkCostVector , solverName.getString() , solverLibraryName.getString () , maxSolverTimeInSeconds.getDouble () , 
082                                "K", Integer.toString(k.getInt ()), 
083                                "maxCopyCapability", Integer.toString(maxCopyCapability.getInt ()) , 
084                                "maxE2ELengthInKm", Double.toString(maxE2ELengthInKm.getDouble ()) , 
085                                "maxE2ENumHops", Integer.toString(maxE2ENumHops.getInt ()) , 
086                                "maxE2EPropDelayInMs", Double.toString(maxE2EPropDelayInMs.getDouble ()) , 
087                                "maxTreeCost", Double.toString(maxTreeCost.getDouble ()) , 
088                                "maxTreeCostFactorRespectToMinimumCostTree", Double.toString(maxTreeCostFactorRespectToMinimumCostTree.getDouble ()) , 
089                                "maxTreeCostRespectToMinimumCostTree", Double.toString(maxTreeCostRespectToMinimumCostTree.getDouble ())));
090                final int P = netPlan.getNumberOfMulticastTrees(); 
091
092                System.out.println ("Number of multicast trees CPL: " + P);
093                
094                /* Create the optimization problem object (JOM library) */
095                OptimizationProblem op = new OptimizationProblem();
096
097                /* Set some input parameters to the problem */
098                op.setInputParameter("u_e", netPlan.getVectorLinkSpareCapacity(), "row"); /* for each link, its unused capacity (the one not used by any mulitcast trees) */
099                op.setInputParameter("A_dp", netPlan.getMatrixMulticastDemand2MulticastTreeAssignment()); /* 1 in position (d,p) if demand d is served by tree p, 0 otherwise */ 
100                op.setInputParameter("A_ep", netPlan.getMatrixLink2MulticastTreeAssignment()); /* 1 in position (e,p) if link e is traversed by tree p, 0 otherwise */
101                op.setInputParameter("h_d", netPlan.getVectorMulticastDemandOfferedTraffic(), "row"); /* for each multicast demand, its offered traffic */
102                op.setInputParameter("h_p", netPlan.getVectorMulticastTreeOfferedTrafficOfAssociatedMulticastDemand () , "row"); /* for each tree, the offered traffic of its demand */
103
104                /* Write the problem formulations */
105                
106                if (optimizationTarget.getString ().equals ("min-consumed-bandwidth")) 
107                {
108                        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 */
109                        op.setObjectiveFunction("minimize", "sum (h_p .* xx_p)"); /* sum of the traffic in the links, proportional to the average number of hops  */
110                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
111                        op.addConstraint("A_ep * (h_p .* xx_p)' <= u_e'"); /* the traffic in each link cannot exceed its capacity  */
112                }
113                else if (optimizationTarget.getString ().equals ("min-av-num-hops")) 
114                {
115                        op.setInputParameter("l_p", netPlan.getVectorMulticastTreeAverageNumberOfHops() , "row"); /* for each tree, the average number of traversed from the ingress, to the different destinations  */
116                        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 */
117                        op.setObjectiveFunction("minimize", "sum (l_p .* h_p .* xx_p)"); /* sum of the traffic in the links, proportional to the average number of hops  */
118                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
119                        op.addConstraint("A_ep * (h_p .* xx_p)' <= u_e'"); /* the traffic in each link cannot exceed its capacity  */
120                }
121                else if (optimizationTarget.getString ().equals ("minimax-link-utilization")) 
122                {
123                        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 */
124                        op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, 1); /* worse case link utilization */
125                        op.setObjectiveFunction("minimize", "rho");
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 * (h_p .* xx_p)' <= rho * u_e'"); /* the traffic in each link cannot exceed its capacity. sets rho as the worse case utilization */
128                }
129                else if (optimizationTarget.getString ().equals ("maximin-link-idle-capacity"))
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 */
132                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* worse case link idle capacity */
133                        op.setObjectiveFunction("maximize", "u");
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 * (h_p .* xx_p)' <= -u + u_e'"); /* the traffic in each link cannot exceed its capacity. sets u as the worse case idle capacity */
136                }
137                else if (optimizationTarget.getString ().equals ("min-av-network-blocking"))
138                {
139                        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");
140                        op.addDecisionVariable("xx_p", false , new int[] { 1, P }, 0, 1); /* the FRACTION of traffic of demand d(p) that is carried by p */
141                        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) */
142                        op.setObjectiveFunction("minimize", "sum(y_e .* erlangB(y_e, u_e))");
143                        op.addConstraint("A_dp * xx_p' == 1"); /* for each demand, the 100% of the traffic is carried (summing the associated paths) */
144                        op.addConstraint("A_ep * (h_p .* xx_p)' == y_e'"); /* sets y_e as the traffic in link e */
145                }
146                else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
147
148                System.out.println ("solverLibraryName: " +  solverLibraryName.getString ());
149                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
150                //op.solve(solverName.getString (), "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
151
152                System.out.println ("solverLibraryName: " +  solverLibraryName.getString ());
153
154                /* If no solution is found, quit */
155                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
156                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
157                
158                /* Save the solution found in the netPlan object */
159                final DoubleMatrix1D h_p = netPlan.getVectorMulticastTreeOfferedTrafficOfAssociatedMulticastDemand();
160                final DoubleMatrix1D xx_p = DoubleFactory1D.dense.make (op.getPrimalSolution("xx_p").to1DArray());
161                final DoubleMatrix1D x_p = xx_p.copy().assign (h_p , DoubleFunctions.mult);
162                netPlan.setVectorMulticastTreeCarriedTrafficAndOccupiedLinkCapacities(x_p , x_p);
163
164                netPlan.removeAllMulticastTreesUnused(PRECISION_FACTOR); // trees with zero traffic (or close to zero, with PRECISION_FACTOR tolerance)
165
166                return "Ok!: The solution found is guaranteed to be optimal (among the given candidate tree list): " + op.solutionIsOptimal() + ". Number multicast trees = " + netPlan.getNumberOfMulticastTrees();
167        }
168
169        @Override
170        public String getDescription()
171        {
172                return "Given a network topology, the capacities in the links, and a set multicast traffic demands, this algorithm permits computing the optimum multicast routing of the traffic (that is, the set ofm multicast trees carrying the traffic of the multicast demand) solving flow-path formulations, that start computing a set of admissible multicast trees (using integer formulations), and then solve the routing problem over them. Through a set of input parameters, the user can choose among different optimization targets and constraints."; 
173        }
174
175        
176        @Override
177        public List<Triple<String, String, String>> getParameters()
178        {
179                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
180                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
181        }
182}