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.DoubleFactory2D;
025import cern.colt.matrix.tdouble.DoubleMatrix1D;
026import cern.colt.matrix.tdouble.DoubleMatrix2D;
027import cern.jet.math.tdouble.DoubleFunctions;
028
029import com.jom.OptimizationProblem;
030import com.net2plan.interfaces.networkDesign.Demand;
031import com.net2plan.interfaces.networkDesign.IAlgorithm;
032import com.net2plan.interfaces.networkDesign.Link;
033import com.net2plan.interfaces.networkDesign.Net2PlanException;
034import com.net2plan.interfaces.networkDesign.NetPlan;
035import com.net2plan.interfaces.networkDesign.NetworkLayer;
036import com.net2plan.interfaces.networkDesign.Node;
037import com.net2plan.utils.Constants.RoutingType;
038import com.net2plan.utils.InputParameter;
039import com.net2plan.utils.Triple;
040
041/**
042 * Solves a general multilayer optimization problem formulation. 
043 * @net2plan.description
044 * @net2plan.keywords Multilayer, Flow assignment (FA), Flow-link formulation, Destination-link formulation, Modular capacities
045 * @net2plan.ocnbooksections Section 7.4
046 * @net2plan.inputParameters 
047 * @author Pablo Pavon-Marino
048 */
049public class Offline_tcfa_generalMultilayer implements IAlgorithm
050{
051        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");
052        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
053        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)");
054        private InputParameter ciurcuitCapacityGbps = new InputParameter ("ciurcuitCapacityGbps", (double) 1.0 , "Capacity of a circuit in Gbps, the assumed units for upper layer traffic" , 0 , false , Double.MAX_VALUE , true);
055        private InputParameter capLowLayerLinksInNumCircuits = new InputParameter ("capLowLayerLinksInNumCircuits", (int) 100 , "The capacity of a lower layer link, measured as the maximum number of circuits that can traverse it." , 1 , Integer.MAX_VALUE);
056
057        private NetworkLayer lowerLayer, upperLayer;
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 (netPlan.getNumberOfLayers() > 2) throw new Net2PlanException ("The design must have one or two layers");
065
066                /* Set a two layer network topology, maybe starting from a single layer design */
067                if (netPlan.isSingleLayer())
068                {
069                        this.lowerLayer = netPlan.getNetworkLayerDefault();
070                        this.upperLayer = netPlan.addLayer("UP LAYER" , "Upper layer of the design" , "Gbps" , "Gbps" , null);
071                        /* Save the demands in the upper layer, and remove them from the lower layer */
072                        for (Demand d : netPlan.getDemands (lowerLayer)) netPlan.addDemand(d.getIngressNode() , d.getEgressNode() , d.getOfferedTraffic() , null , upperLayer);
073                }
074                else
075                {
076                        this.lowerLayer = netPlan.getNetworkLayer(0);
077                        this.upperLayer = netPlan.getNetworkLayer(1);
078                }
079                netPlan.setRoutingType(RoutingType.HOP_BY_HOP_ROUTING, upperLayer);
080                netPlan.setRoutingType(RoutingType.SOURCE_ROUTING, lowerLayer);
081
082                /* Initialize some variables */
083                final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor"));
084                final int N = netPlan.getNumberOfNodes();
085                final int D_up = netPlan.getNumberOfDemands (upperLayer);
086                final int E_lo = netPlan.getNumberOfLinks (lowerLayer);
087                if (N == 0 || D_up == 0) throw new Net2PlanException("This algorithm requires a topology and a demand set");
088
089                netPlan.removeAllLinks(upperLayer);
090                netPlan.removeAllDemands(lowerLayer);
091                netPlan.setLinkCapacityUnitsName("Gbps" , lowerLayer);
092                netPlan.setLinkCapacityUnitsName("Gbps" , upperLayer);
093                netPlan.setDemandTrafficUnitsName("Gbps" , lowerLayer);
094                netPlan.setDemandTrafficUnitsName("Gbps" , upperLayer);
095                netPlan.setVectorLinkCapacity(DoubleFactory1D.dense.make (E_lo , capLowLayerLinksInNumCircuits.getInt() * ciurcuitCapacityGbps.getDouble()) , lowerLayer);
096                
097                /* Create a full mesh of upper layer links in the netPlan object (index "c" in the variables), coupled to the
098                 * corresponding demand in the lower layer */
099                for (Node i : netPlan.getNodes ()) for (Node j : netPlan.getNodes ()) if (i != j)
100                {
101                        if ((i.getIndex() == 0) && (j.getIndex() == 1)) continue;
102                        final Link link = netPlan.addLink (i, j,0 , netPlan.getNodePairEuclideanDistance(i, j), 200000 , null , upperLayer);
103                        final Demand demand = netPlan.addDemand(i, j, 0, null, lowerLayer);
104                        if (link.getIndex() != demand.getIndex()) throw new RuntimeException ("Bad");
105                        link.coupleToLowerLayerDemand(demand);
106                }
107                                        
108                /* Compute the distances of the potential links */
109                final int E_ul = netPlan.getNumberOfLinks(upperLayer);
110                final int E_ll = netPlan.getNumberOfLinks(lowerLayer);
111
112                /* Create the optimization problem object (JOM library) */
113                OptimizationProblem op = new OptimizationProblem();
114
115                op.addDecisionVariable("x_tc", false , new int[] { N, E_ul }, 0, Double.MAX_VALUE); /* the amount of traffic targeted to node t, that is carried by link c (upper layer virtual link) */
116                op.addDecisionVariable("z_c", true , new int[] { 1 , E_ul }, 0, Double.MAX_VALUE); /* number of circuits established between end nodes of virtual link c  */
117                op.addDecisionVariable("x_ce", true , new int[] { E_ul , E_ll }, 0, Double.MAX_VALUE); /* number of circuits corresponding to virtual link c, that traverse low layer link e */
118
119                /* Set some input parameters */
120                op.setInputParameter("A_nc", netPlan.getMatrixNodeLinkIncidence(upperLayer)); /* 1 in position (n,e) if link e starts in n, -1 if it ends in n, 0 otherwise */
121                final DoubleMatrix1D egressTraffic_t = netPlan.getVectorNodeEgressUnicastTraffic(upperLayer);
122                final DoubleMatrix2D trafficMatrixDiagonalNegative = netPlan.getMatrixNode2NodeOfferedTraffic(upperLayer);
123                trafficMatrixDiagonalNegative.assign (DoubleFactory2D.sparse.diagonal(egressTraffic_t) , DoubleFunctions.minus);
124                op.setInputParameter("TM", trafficMatrixDiagonalNegative);
125                op.setInputParameter("U_hi", ciurcuitCapacityGbps.getDouble());
126                op.setInputParameter("U_lo", capLowLayerLinksInNumCircuits.getInt());
127                op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence(lowerLayer)); /* 1 in position (n,e) if link e starts in n, -1 if it ends in n, 0 otherwise */
128                op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(upperLayer) , "row");
129                op.setInputParameter("EPSILON", 0.001 / (E_ul * netPlan.getVectorDemandOfferedTraffic(upperLayer).zSum()));
130                
131                /* Sets the objective function */
132                op.setObjectiveFunction("minimize", "sum(z_c) + EPSILON * sum(x_tc) + EPSILON*sum(x_ce)");
133
134                /* Compute some matrices required for writing the constraints */
135                op.addConstraint("A_nc * (x_tc') == TM"); /* the flow-conservation constraints (NxE_hi constraints) */
136                op.addConstraint("sum(x_tc,1) <= U_hi * z_c"); /* the capacity constraints (E_hi constraints) */
137                op.addConstraint("A_ne * (x_ce') == A_nc * diag(z_c)"); /* the lower layer flow-conservation constraints (NxE_hi constraints) */
138                op.addConstraint("sum(x_ce,1) <= U_lo"); /* the capacity constraints (E constraints) */
139
140                /* Call the solver to solve the problem */
141                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
142
143                /* If no solution is found, quit */
144                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
145                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
146                
147                /* Retrieve the optimum solutions */
148                final DoubleMatrix1D z_c = op.getPrimalSolution("z_c").view1D();
149                final DoubleMatrix2D x_tc = op.getPrimalSolution("x_tc").view2D();
150                final DoubleMatrix2D x_ce = op.getPrimalSolution("x_ce").view2D();
151
152                /* Sets the routing in both layers, which also establish the capacity in the upper layer links */
153                netPlan.setRoutingFromDemandLinkCarriedTraffic(x_ce.copy ().assign(DoubleFunctions.mult(ciurcuitCapacityGbps.getDouble())) , false , true , lowerLayer);
154                netPlan.setRoutingFromDestinationLinkCarriedTraffic(x_tc , true , upperLayer); // remove the cycles if any
155
156                for (Link eHi : netPlan.getLinks (upperLayer))
157                        if (Math.abs(eHi.getCapacity() - ciurcuitCapacityGbps.getDouble() * z_c.get(eHi.getIndex())) > 1e-3) throw new RuntimeException ("Bad");
158                netPlan.removeAllLinksUnused (PRECISION_FACTOR , upperLayer);
159
160                /* check */
161                if (netPlan.getVectorDemandBlockedTraffic(upperLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad: " + netPlan.getVectorDemandBlockedTraffic(upperLayer));
162                if (netPlan.getVectorDemandBlockedTraffic(lowerLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad");
163                if (netPlan.getVectorLinkOversubscribedTraffic(upperLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad");
164                if (netPlan.getVectorLinkOversubscribedTraffic(lowerLayer).zSum() > PRECISION_FACTOR) throw new RuntimeException ("Bad");
165                
166                return "Ok! Num circuits: " + Math.round(netPlan.getVectorLinkCapacity(upperLayer).zSum() / ciurcuitCapacityGbps.getDouble());
167        }
168
169        @Override
170        public String getDescription()
171        {
172                return "Given a network composed of two layers, with traffic demands defined at the upper layer and links defined at the lower. The upper laye traffic is supposed to be routed through fixed capacity circuits. Each circuit, which is a direct link or the upper layer, is actually realized by a demand in the lower layer, that is routed through the lower layer links. Each lower layer link can host a given number of circuits traversing it. The algorithm searches for (i) the circuits to establish, (ii) the routing of the upper layer over the circuits, and (iii) the routing of the circuits over the lower layer links. The target is minimizing the number of circuits needed, a measure of the network cost. For finding the solution, the algorithm solves using JOM a formulation that combines a destination-link formulation in the upper layer routing, and a flow-link formulation in the lower layer. ";
173        }
174
175        @Override
176        public List<Triple<String, String, String>> getParameters()
177        {
178                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
179                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
180        }
181}