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 *******************************************************************************/
011package com.net2plan.examples.general.offline;
012
013
014import cern.colt.list.tdouble.DoubleArrayList;
015import cern.colt.list.tint.IntArrayList;
016import cern.colt.matrix.tdouble.DoubleFactory2D;
017import cern.colt.matrix.tdouble.DoubleMatrix2D;
018import com.jom.DoubleMatrixND;
019import com.jom.OptimizationProblem;
020import com.net2plan.interfaces.networkDesign.*;
021import com.net2plan.libraries.WDMUtils;
022import com.net2plan.utils.Constants.RoutingType;
023import com.net2plan.utils.InputParameter;
024import com.net2plan.utils.IntUtils;
025import com.net2plan.utils.Pair;
026import com.net2plan.utils.Triple;
027
028import java.util.*;
029
030/**
031 * Algorithm based on an ILP solving the Routing, Spectrum, Modulation Assignment (RSMA) problem with regenerator placement, in flexi (elastic) or fixed grid optical WDM networks, with or without fault tolerance, latency and/or lightpath bidirectionality requisites.
032 * 
033 * <p>The input design is assumed to have a WDM layer compatible with {@link com.net2plan.libraries.WDMUtils WDMUtils} Net2Plan 
034 * library usual assumptions:</p>
035 * <ul>
036 * <li>Each network node is assumed to be an Optical Add/Drop Multiplexer WDM node</li>
037 * <li>Each network link at WDM layer is assumed to be an optical fiber.</li>
038 * <li>The spectrum in the fibers is assumed to be composed of a number of frequency slots. 
039 * In fixed-grid network, each frequency slot would correspond to a wavelength channel. 
040 * In flexi-grid networks, it is just a frequency slot, and lightpaths can occupy more than one. In any case, 
041 * two lightpaths that use overlapping frequency slots cannot traverse the same fiber, since their signals would mix.</li>
042 * <li>Each traffic demand is a need to transmit an amount of Gbps between two nodes. 
043 * A demand traffic can be carried using one or more lightpaths.</li>
044 * </ul>
045 * 
046 * <p>Each lightpath produced by the design is returned as a {@code Route} object. Protection lightpaths in 1+1 case 
047 * are returned as ProtectionSegment objects attached to the {@code Route}. They represent a set of reserved frequency slots in 
048 * a set of fibers, to be used to protect other lightpaths.</p>
049 * 
050 * <p>Each lightpath starts and ends in a transponder. The user is able to define a set of available transpoder types, so 
051 * the design can create lightpaths using any combination of them. The information user-defined per transponder is:</p>
052 * <ul>
053 * <li>Line rate in Gbps (typically 10, 40, 100 in fixed-grid cases, and other multiples in flexi-grid networks).</li> 
054 * <li>Cost</li> 
055 * <li>Number of frequency slots occupied (for a given line rate, this depends on the modulation the transponder uses)</li> 
056 * <li>Optical reach in km: Maximum allowed length in km of the lightpaths with this transponder. 
057 * Higher distances can be reached using signal regenerators.</li> 
058 * <li>Cost of a regenerator for this transponder. Regenerators can be placed at intermdiate nodes of the lightpath route, 
059 * regenerate its optical signal, and then permit extending its reach. We consider that regenerators cannot change the 
060 * frequency slots occupied by the lightpath (that is, they are not capable of wavelength conversion)</li> 
061 * </ul>
062 * <p> In addition, the user can force the design to use bidirectional transponders (the usual case). This means that (i) in 
063 * each transponder we have the transmission and reception side inseparable (so you cannot e.g. buy just the transmission side), 
064 * and (ii) a couple of transponders (of course of the same type) being the end points of a lightpath from node 1 to node 2, 
065 * also are used for a lightpath from node 2 to node 1, (iii) note however that the two opposite lightpaths can follow arbitrary routes 
066 * (they do not have to traverse the reversed sequence of nodes). This bidirectionality constraint is a common requirement if 
067 * the lightpath will be used for carrying IP traffic, since IP assumes that its links (the lightpaths) are bidirectional pipes.</p>
068 * 
069 * <p>We assume that all the fibers use the same wavelength grid, composed of a user-defined number of frequency slots. 
070 * The user can also select a limit in the maximum propagation delay of a lightpath. </p>
071 * <p>The output design consists in the set of lightpaths to establish, in the 1+1 case also with a 1+1 lightpath each. 
072 * Each lightpath is characterized by the transponder type used (which sets its line rate and number of occupied slots in the 
073 * traversed fibers), the particular set of contiguous frequency slots occupied, and the set of signal regeneration points (if any). 
074 * This information is stored in the {@code Route} and {@code ProtectionSegment} object using the regular methods in WDMUTils, 
075 * and can be retrieved in the same form (e.g. by a report showing the WDM network information). 
076 * If a feasible solution is not found (one where all the demands are satisfied with the given constraints), a message is shown.</p>.  
077 * 
078 * <h2>Failure tolerance</h2>
079 * <p>The user can choose among three possibilities for designing the network:</p>
080 * <ul>
081 * <li>No failure tolerant: The lightpaths established should be enough to carry the traffic of all the demands when no failure 
082 * occurs in the network, but any losses are accepted if the network suffers failures in links or nodes.</li>
083 * <li>Tolerant to single-SRG (Shared Risk Group) failures with static lightpaths: All the traffic demands should be satisfied using 
084 * lightpaths, so that under any single-SRG failure (SRGs are taken from the input design), the surviving lightpaths are enough 
085 * to carry the 100% of the traffic. Note that lightpaths are static, in the sense that they are not rerouted when affected by a 
086 * failure (they just also fail), and the design should just overprovision the number of lightpaths to establish with that in mind.</li>
087 * <li>1+1 SRG-disjoint protection: This is another form to provide single-SRG failure tolerance. Each lightpath is backed up by 
088 * a SRG-disjoint lightpath (returned as a {@code ProtectionSegment} object). The backup lightpath uses the same type of transponder 
089 * as the primary (and thus the same line rate, an occupies the same number of slots), its path is SRG-disjoint, and the particular 
090 * set of slots occupied can be different. </li>
091 * </ul>
092 * <h2>Optimization targets</h2>
093 * <p>The user can choose between two optimization targets:</p>
094 * <ul>
095 * <li>Minimizing the total cost, given by the transponders and regenerators (if any).</li>
096 * <li>Minimizing congestion at the WDM layer. This means looking for the design that maximizes the number of idle slots 
097 * in the bottleneck fiber (the one with less idle frequency slots). </li>
098 * </ul>
099 * <h2>Use cases</h2>
100 * <p>This algorithm is quite general, and fits a number of use cases designing WDM networks, for instance:</p>
101 * <ul>
102 * <li>Single line rate, fixed grid networks: Then, one single type of transponder will be available, which occupies one frequency slot</li>
103 * <li>Mixed-Line Rate fixed-grid networks: In this case, several transponders can be available at different line rates and with different optical 
104 * reaches. However, all of them occupy one slot (one wavelength channel)</li>
105 * <li>Single line rate, flexi-grid networks using varying-modulation transponders: Several transponders are available (or the same 
106 * transponder with varying configurations), all of them with the same line rate, but thanks to the different usable modulations 
107 * they can have different optical reaches and/or number of occupied slots.</li>
108 * <li>Multiple line rate, flexi-grid networks using Bandwidth Variable Transponders: Here, it is possible to use different transponders 
109 * with different line rates, e.g. to reflect more sophisticated transponders which can have different configurations, varying its line rate, 
110 * optical reach, and number of occupied slots.</li>
111 * <li>...</li>
112 * </ul>
113 * <h2>Some details of the algorithm</h2>
114 * <p>The algorithm is based on solving a set of MILPs (Mixed Integer Linear Programs) interfacing from JOM to the user-defined 
115 * solver. The algorithm uses a flow-path formulation, where a number of candidate paths are pre-computed for each demand. The 
116 * user-defined parameter {@code k} limits the maximum number of paths computed per demand. In the 1+1 case, the usable SRG-disjoint 
117 * path pairs for each demand are computed from the candidate paths. Increasing the number of paths {@code k} also increases 
118 * the computational complexity of the algorithm, but can produce better solutions. In some occasions, a low {@code k} number is the 
119 * reason for the algorithm failing in finding a feasible solution.</p>
120 * <p>The details of the algorithm will be provided in a publication currently under elaboration.</p>
121 * 
122 * @net2plan.keywords JOM, WDM
123 * @net2plan.inputParameters 
124 * @author Pablo Pavon-Marino
125 */
126@SuppressWarnings("unchecked")
127public class Offline_ipOverWdm_routingSpectrumAndModulationAssignmentILPNotGrooming implements IAlgorithm
128{
129        private InputParameter k = new InputParameter ("k", (int) 5 , "Maximum number of admissible paths per input-output node pair" , 1 , Integer.MAX_VALUE);
130        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");
131        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "" , "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
132        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)");
133        private InputParameter numFrequencySlotsPerFiber = new InputParameter ("numFrequencySlotsPerFiber", (int) 40 , "Number of wavelengths per link" , 1, Integer.MAX_VALUE);
134        private InputParameter transponderTypesInfo = new InputParameter ("transponderTypesInfo", "10 1 1 9600 1" , "Transpoder types separated by \";\" . Each type is characterized by the space-separated values: (i) Line rate in Gbps, (ii) cost of the transponder, (iii) number of slots occupied in each traversed fiber, (iv) optical reach in km (a non-positive number means no reach limit), (v) cost of the optical signal regenerator (regenerators do NOT make wavelength conversion ; if negative, regeneration is not possible).");
135        private InputParameter ipLayerIndex = new InputParameter ("ipLayerIndex", (int) 1 , "Index of the IP layer (-1 means default layer)");
136        private InputParameter wdmLayerIndex = new InputParameter ("wdmLayerIndex", (int) 0 , "Index of the WDM layer (-1 means default layer)");
137        private InputParameter networkRecoveryType = new InputParameter ("networkRecoveryType", "#select# not-fault-tolerant single-srg-tolerant-static-lp 1+1-srg-disjoint-lps" , "Establish if the design should be tolerant or not to single SRG failures (SRGs are as defined in the input NetPlan). First option is that the design should not be fault tolerant, the second means that failed lightpaths are not recovered, but an overprovisioned should be made so enough lightpaths survive to carry all the traffic in every failure. The third means that each lightpath is 1+1 protceted by a SRG-disjoint one, that uses the same transponder");
138        private InputParameter optimizationTarget = new InputParameter ("optimizationTarget", "#select# min-cost maximin-fiber-number-idle-slots" , "Type of optimization target. Choose among minimize the network cost given by the su mof the transponders cost, and maximize the number of idle frequency slots in the fiber with less idle frequency slot");
139        private InputParameter maxPropagationDelayMs = new InputParameter ("maxPropagationDelayMs", (double) -1 , "Maximum allowed propagation time of a lighptath in miliseconds. If non-positive, no limit is assumed");
140        private InputParameter bidirectionalTransponders = new InputParameter ("bidirectionalTransponders", true , "If true, the transponders used are bidirectional. Then, the number of lightpaths of each type from node 1 to node 2, equals the number of lightpahts from 2 to 1 (see that both directions can have different routes and slots)");
141        private NetworkLayer wdmLayer, ipLayer;
142        private Demand.IntendedRecoveryType recoveryTypeNewLps;
143
144        @Override
145        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
146        {
147                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
148                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
149
150                /* Create a two-layer IP over WDM design if the input is single layer */
151                if (netPlan.getNumberOfLayers() == 1)
152                {
153                        this.wdmLayer = netPlan.getNetworkLayerDefault();
154                        netPlan.setDemandTrafficUnitsName("Gbps");
155                        netPlan.setLinkCapacityUnitsName("Frequency slots");
156                        this.ipLayer = netPlan.addLayer("IP" , "IP layer" , "Gbps" , "Gbps" , null , null);
157                        for (Demand wdmDemand : netPlan.getDemands(wdmLayer))
158                                netPlan.addDemand(wdmDemand.getIngressNode(), wdmDemand.getEgressNode() , wdmDemand.getOfferedTraffic() , RoutingType.SOURCE_ROUTING , wdmDemand.getAttributes() , ipLayer);
159                }
160                else
161                {
162                        this.wdmLayer = wdmLayerIndex.getInt () == -1? netPlan.getNetworkLayerDefault() : netPlan.getNetworkLayer(wdmLayerIndex.getInt ());
163                        this.ipLayer = ipLayerIndex.getInt () == -1? netPlan.getNetworkLayerDefault() : netPlan.getNetworkLayer(ipLayerIndex.getInt ());
164                }
165
166                final NetworkLayer wdmLayer = wdmLayerIndex.getInt () == -1? netPlan.getNetworkLayerDefault() : netPlan.getNetworkLayer(wdmLayerIndex.getInt ());
167
168                /* Basic checks */
169                final int N = netPlan.getNumberOfNodes();
170                final int Ewdm = netPlan.getNumberOfLinks(wdmLayer);
171                final int Dip = netPlan.getNumberOfDemands(ipLayer);
172                final int S = numFrequencySlotsPerFiber.getInt();
173                if (N == 0 || Ewdm == 0 || Dip == 0) throw new Net2PlanException("This algorithm requires a topology with links and a demand set");
174
175                if (networkRecoveryType.getString().equals("not-fault-tolerant") || networkRecoveryType.getString().equals("single-srg-tolerant-static-lp"))
176                        recoveryTypeNewLps = Demand.IntendedRecoveryType.NONE;
177                else if (networkRecoveryType.getString().equals("1+1-srg-disjoint-lps"))
178                        recoveryTypeNewLps = Demand.IntendedRecoveryType.PROTECTION_REVERT;
179                else throw new Net2PlanException ("Wrong input parameters");
180
181                /* Store transpoder info */
182                WDMUtils.TransponderTypesInfo tpInfo = new WDMUtils.TransponderTypesInfo(transponderTypesInfo.getString());
183                final int T = tpInfo.getNumTypes();
184                
185                /* Remove all routes in current netPlan object. Initialize link capacities and attributes, and demand offered traffic */
186                netPlan.removeAllLinks (ipLayer);
187                netPlan.removeAllDemands (wdmLayer);
188                netPlan.removeAllMulticastDemands(wdmLayer);
189
190                /* Compute the candidate path list of possible paths */
191                final SortedMap<Pair<Node,Node>,List<List<Link>>> cpl = netPlan.computeUnicastCandidatePathList(netPlan.getVectorLinkLengthInKm(wdmLayer) , k.getInt(), tpInfo.getMaxOpticalReachKm() , -1, maxPropagationDelayMs.getDouble(), -1, -1, -1 , null , wdmLayer);
192                final SortedMap<Pair<Node,Node>,List<Pair<List<Link>,List<Link>>>> cpl11 = networkRecoveryType.getString().equals("1+1-srg-disjoint-lps")? NetPlan.computeUnicastCandidate11PathList(cpl,0) : null;
193                
194                /* Compute the CPL, adding the routes */
195                /* 1+1 case: as many routes as 1+1 valid pairs (then, the same sequence of links can be in more than one Route). The route index and segment index are the same (1+1 pair index) */
196                /* rest of the cases: each sequence of links appears at most once */
197                Map<Link,Double> linkLengthMap = new HashMap<Link,Double> (); for (Link e : netPlan.getLinks(wdmLayer)) linkLengthMap.put(e , e.getLengthInKm());
198                final int maximumNumberOfPaths = T*k.getInt()*Dip;
199                List<Integer> transponderType_p = new ArrayList<Integer> (maximumNumberOfPaths);
200                List<Double> cost_p = new ArrayList<Double> (maximumNumberOfPaths); 
201                List<Double> lineRate_p = new ArrayList<Double> (maximumNumberOfPaths); 
202                List<Integer> numSlots_p = new ArrayList<Integer> (maximumNumberOfPaths);
203                List<List<Link>> seqLinks_p = new ArrayList<List<Link>> (maximumNumberOfPaths);
204                List<List<Link>> seqLinks2_p = cpl11 == null? null : new ArrayList<List<Link>> (maximumNumberOfPaths);
205                List<int []> regPositions_p = new ArrayList<int []> (maximumNumberOfPaths);
206                List<int []> regPositions2_p = new ArrayList<int []> (maximumNumberOfPaths);
207                List<Demand> ipDemand_p = new ArrayList<Demand> (maximumNumberOfPaths);
208                for (Demand ipDemand : netPlan.getDemands(ipLayer))
209                {
210                        ipDemand.setRoutingType(RoutingType.SOURCE_ROUTING);
211                        boolean atLeastOnePathOrPathPair = false;
212                        for (int t = 0 ; t < T ; t ++)
213                        {
214                                final Pair<Node,Node> nodePair = Pair.of(ipDemand.getIngressNode() , ipDemand.getEgressNode());
215                                final double regeneratorCost = tpInfo.getRegeneratorCost(t);
216                                final boolean isRegenerable = regeneratorCost >= 0;
217                                for (Object sp : cpl11 != null? cpl11.get(nodePair) : cpl.get(nodePair))
218                                {
219                                        List<Link> firstPath = (cpl11 == null)? ((List<Link>) sp) : ((Pair<List<Link>,List<Link>>) sp).getFirst(); 
220                                        List<Link> secondPath = (cpl11 == null)? null : ((Pair<List<Link>,List<Link>>) sp).getSecond (); 
221                                        if (!isRegenerable && (getLengthInKm(firstPath) > tpInfo.getOpticalReachKm(t))) break;
222                                        if (secondPath != null) if (!isRegenerable && (getLengthInKm(secondPath) > tpInfo.getOpticalReachKm(t))) break;
223
224                                        final int [] regPositions1 = isRegenerable? WDMUtils.computeRegeneratorPositions(firstPath , tpInfo.getOpticalReachKm(t)) : new int [firstPath.size()];
225                                        final int [] regPositions2 = cpl11 == null? null : isRegenerable? WDMUtils.computeRegeneratorPositions(secondPath , tpInfo.getOpticalReachKm(t)) : new int [secondPath.size()];
226                                        final int numRegeneratorsNeeded = !isRegenerable? 0 : (int) IntUtils.sum(regPositions1) + (secondPath == null? 0 : (int) IntUtils.sum(regPositions2)) ;
227                                        final double costOfLightpathOr11Pair = tpInfo.getCost(t) * (cpl11 != null? 2 : 1) + (tpInfo.getRegeneratorCost(t) * numRegeneratorsNeeded);
228
229                                        cost_p.add (costOfLightpathOr11Pair);
230                                        transponderType_p.add (t);
231                                        lineRate_p.add(tpInfo.getLineRateGbps(t));
232                                        numSlots_p.add(tpInfo.getNumSlots(t));
233                                        ipDemand_p.add(ipDemand);
234                                        seqLinks_p.add(firstPath);
235                                        regPositions_p.add(regPositions1);
236                                        if (cpl11 != null) { seqLinks2_p.add(secondPath); regPositions2_p.add(regPositions2); }
237                                        atLeastOnePathOrPathPair = true;
238                                }
239                        }
240                        if (!atLeastOnePathOrPathPair) throw new Net2PlanException ("There are no possible routes (or 1+1 pairs) for a demand (" + ipDemand + "). The topology may be not connected enough, or the optical reach may be too small");
241                }
242                final int P = transponderType_p.size(); // one per potential sequence of links (or 1+1 pairs of sequences) and transponder
243
244                /* Compute some important matrices for the formulation */
245                DoubleMatrix2D A_dp = DoubleFactory2D.sparse.make(Dip,P); /* 1 is path p is assigned to demand d */
246                DoubleMatrix2D A_ep = DoubleFactory2D.sparse.make(Ewdm,P); /* 1 if path (or primary path in 1+1) p travserses link e */
247                DoubleMatrix2D A2_ep = DoubleFactory2D.sparse.make(Ewdm,P); /* 1 if backup path of pair p traverses link e */
248                DoubleMatrix2D A_psrg = DoubleFactory2D.sparse.make(P,netPlan.getNumberOfSRGs()); /* 1 if path p fails when srg fails */
249                double [][] feasibleAssignment_ps = new double [P][S];
250                DoubleMatrix2D [] A_n1Mn2p = new DoubleMatrix2D [T];
251                if (bidirectionalTransponders.getBoolean())
252                        for (int t = 0 ; t < T ; t ++) A_n1Mn2p [t] = DoubleFactory2D.sparse.make(N*N , P);
253                for (int p = 0 ; p < P ; p ++)
254                {
255                        A_dp.set(ipDemand_p.get(p).getIndex() , p , 1.0);
256                        for (Link e : seqLinks_p.get(p)) A_ep.set (e.getIndex() , p , 1.0);
257                        if (cpl11 != null) for (Link e : seqLinks2_p.get(p)) A2_ep.set (e.getIndex() , p , 1.0);
258                        if (networkRecoveryType.getString().equals("single-srg-tolerant-static-lp"))
259                                for (Link e : seqLinks_p.get(p))
260                                {
261                                        for (SharedRiskGroup srg : e.getSRGs()) A_psrg.set(p,srg.getIndex(),1.0);
262                                        for (SharedRiskGroup srg : e.getOriginNode().getSRGs()) A_psrg.set(p,srg.getIndex(),1.0);
263                                        for (SharedRiskGroup srg : e.getDestinationNode().getSRGs()) A_psrg.set(p,srg.getIndex(),1.0);
264                                }
265                        for (int s = 0; s < S + 1 - numSlots_p.get(p) ; s ++)
266                                feasibleAssignment_ps [p][s] = 1;
267                        if (bidirectionalTransponders.getBoolean())
268                        {
269                                final int t = transponderType_p.get(p);
270                                final int n1 = ipDemand_p.get(p).getIngressNode().getIndex();
271                                final int n2 = ipDemand_p.get(p).getEgressNode().getIndex();
272                                final int nLower = n1 < n2? n1 : n2;
273                                final int nGreater = n1 > n2? n1 : n2;
274                                A_n1Mn2p [t].set(nLower + N * nGreater , p , nLower == n1? 1.0 : -1.0);
275                        }
276                }
277                
278                
279                /* Create the optimization problem object (JOM library) */
280                OptimizationProblem op = new OptimizationProblem();
281
282                /* Add the decision variables to the problem */
283                /* p is the route index and s the initial slot. In 1+1, p is the 1+1 pair index (equal to the route and segment indexes), s the initial slot of the primary (route)   */
284                op.addDecisionVariable("x_ps", true, new int[] {P, S}, new DoubleMatrixND (new int [] {P,S}) , new DoubleMatrixND (feasibleAssignment_ps)); /* 1 if lightpath d(p) is routed through path p in wavelength w */
285                if (cpl11 != null)
286                        /* p is the 1+1 pair index (equal to the route and segment indexes), s the initial slot of the backup (segment)   */
287                        op.addDecisionVariable("x2_ps", true, new int[] {P, S}, new DoubleMatrixND (new int [] {P,S}) , new DoubleMatrixND (feasibleAssignment_ps)); /* 1 if lightpath d(p) is routed through path p in wavelength w */
288                
289                /* Set some input parameters */
290                op.setInputParameter("S", S);
291                op.setInputParameter("h_d", netPlan.getVectorDemandOfferedTraffic(ipLayer), "row");
292                op.setInputParameter("rate_p", lineRate_p , "row");
293                op.setInputParameter("c_p", cost_p , "row");
294                op.setInputParameter("A_dp", A_dp);
295                op.setInputParameter("A_ep", A_ep); // in 1+1, only occupation of the primaries (p is the 1+1 pair index, equal to route and segment indexes)
296                if (cpl11 != null)
297                        op.setInputParameter("A2_ep", A2_ep); 
298                
299                /* Sets the objective function */
300                if (optimizationTarget.getString().equals("min-cost"))
301                        op.setObjectiveFunction("minimize", "sum(c_p * x_ps)"); /* sum_ps (c_p ยท x_ps). In 1+1 the cost is multiplied by two */
302                else if (optimizationTarget.getString().equals("maximin-fiber-number-idle-slots"))
303                {
304                        op.addDecisionVariable("u", true, new int[] {1, 1} , 0 , S); /* Number of idle slots in the worst case fiber */
305                        op.setObjectiveFunction("maximize", "u");
306                        op.setInputParameter("numSlots_p", numSlots_p , "row");
307                        if (cpl11 == null)
308                                op.addConstraint("sum(A_ep * diag(numSlots_p) * x_ps , 2) <= S - u");
309                        else
310                                op.addConstraint("sum(A_ep * diag(numSlots_p) * x_ps + A2_ep * diag(numSlots_p) * x2_ps , 2) <= S - u");
311                }
312                        
313                /* Carry enough traffic in each demand to satisfy the minimum traffic to carry (no failure state) */
314                /* sum_{s , p \in P_d} rate_p x_ps >= h_d, for each d */
315                op.addConstraint("A_dp * diag (rate_p) * x_ps * ones([S; 1]) >= h_d'"); /* each lightpath d: is carried in exactly one p-w --> sum_{p in P_d, w} x_dp <= 1, for all d */
316                if (cpl11 != null)
317                        op.addConstraint("sum(x_ps,2) == sum(x2_ps,2)"); /* The number of lightpath in primary of 1+1 pair p and inthe backup is the same  */
318
319                /* (no 1+1, but fault tolerant) Carry enough traffic in each demand to satisfy the minimum traffic to carry, in all of the single-SRG failure states */
320                if (networkRecoveryType.getString().equals("single-srg-tolerant-static-lp"))
321                {
322                        /* sum_{s , p \in P_d, p survives} rate_p x_ps >= h_d, for each d, for each srg */
323                        for (int srg = 0 ; srg < A_psrg.columns() ; srg ++)
324                        {
325                                /* Asrg_pp_ Diagonal pxp matrix, with a one for surviving paths */
326                                DoubleMatrix2D Asrg_pp = DoubleFactory2D.sparse.make(P,P);
327                                for (int p = 0; p < P ; p ++) Asrg_pp.set(p,p,1 - A_psrg.get(p , srg));
328                                op.setInputParameter("Asrg_pp" , Asrg_pp);
329                                op.addConstraint("A_dp * Asrg_pp * diag (rate_p) * x_ps * ones([S; 1]) >= h_d'"); /* each lightpath d: is carried in exactly one p-w --> sum_{p in P_d, w} x_dp <= 1, for all d */
330                        }
331                }
332                
333                /* Frequency-slot clashing */
334                /* \sum_t \sum_{p \in P_e, sinit {s-numSlots(t),s} x_ps <= 1, for each e, s   */
335                String constraintString = "";
336                for (int t = 0; t < T ; t ++)
337                {
338                        {
339                                final String name_At_pp = "A" + Integer.toString(t) + "_pp";
340                                final String name_At_s1s2 = "A" + Integer.toString(t) + "_s1s2";
341                                /* At_pp, diagonal matrix, 1 if path p is associated to a transponder of type t */
342                                DoubleMatrix2D At_pp = DoubleFactory2D.sparse.make(P,P);
343                                int p = 0; for (int type : transponderType_p) { if (type == t) At_pp.set(p,p,1.0); p++; }
344                                /* At_s1s2, upper triangular matrix, 1 if a transponder of type with initial slot s1, occupied slots s2 (depends on number of slots occupied) */
345                                DoubleMatrix2D At_s1s2 = DoubleFactory2D.sparse.make(S,S);
346                                for (int s1 = 0 ; s1 < S ; s1 ++)
347                                        for (int cont = 0 ; cont < tpInfo.getNumSlots(t) ; cont ++)
348                                                if (s1 - cont >= 0) At_s1s2.set(s1-cont,s1,1.0); 
349                                op.setInputParameter(name_At_pp, At_pp);
350                                op.setInputParameter(name_At_s1s2, At_s1s2);
351                                constraintString += (t == 0? "" : " + ") + "( A_ep * " + name_At_pp + " * x_ps * " + name_At_s1s2 + " ) "; 
352                        }
353
354                        if (cpl11 != null) // sum also the slots occupied by the 
355                        {
356                                final String name_A2t_pp = "A2" + Integer.toString(t) + "_pp";
357                                final String name_A2t_s1s2 = "A2" + Integer.toString(t) + "_s1s2";
358                                /* At_pp, diagonal matrix, 1 if path p is associated to a transponder of type t */
359                                DoubleMatrix2D A2t_pp = DoubleFactory2D.sparse.make(P,P);
360                                int p = 0; for (int type : transponderType_p) { if (type == t) A2t_pp.set(p,p,1.0); p++; }
361                                /* At_s1s2, upper triangular matrix, 1 if a transponder of type with initial slot s1, occupied slots s2 (depends on number of slots occupied) */
362                                DoubleMatrix2D A2t_s1s2 = DoubleFactory2D.sparse.make(S,S);
363                                for (int s1 = 0 ; s1 < S ; s1 ++)
364                                        for (int cont = 0 ; cont < tpInfo.getNumSlots(t) ; cont ++)
365                                                if (s1 - cont >= 0) A2t_s1s2.set(s1-cont,s1,1.0); 
366                                op.setInputParameter(name_A2t_pp, A2t_pp);
367                                op.setInputParameter(name_A2t_s1s2, A2t_s1s2);
368                                constraintString += " + ( A2_ep * " + name_A2t_pp + " * x2_ps * " + name_A2t_s1s2 + " ) "; 
369                        }
370                }               
371                op.addConstraint(constraintString + " <= 1"); /* wavelength-clashing constraints --> sum_{p in P_e, w} x_pw <= 1, for all e,w */
372
373                /* Bidirectional constraints */
374                if (bidirectionalTransponders.getBoolean())
375                {
376                        for (int t = 0 ; t < T ; t ++)
377                        {
378                                op.setInputParameter("At_n1Mn2p" , A_n1Mn2p [t]);
379                                if (cpl11 != null)
380                                        op.addConstraint("sum (At_n1Mn2p * (x_ps + x2_ps) , 2) == 0");
381                                else
382                                        op.addConstraint("sum (At_n1Mn2p * x_ps , 2) == 0");
383                        }
384                }
385                
386                /* Call the solver to solve the problem */
387                op.solve(solverName.getString(), "solverLibraryName", solverLibraryName.getString() , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble());
388
389                /* If a feasible solution was not found, quit (this may also happen if after the maximum solver time no feasible solution is found) */
390                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
391
392                /* Retrieve the optimum solutions */
393                DoubleMatrix2D x_ps = op.getPrimalSolution("x_ps").view2D();
394                DoubleMatrix2D x2_ps = cpl11 == null? null : op.getPrimalSolution("x2_ps").view2D();
395
396                /* Create the lightpaths according to the solutions given */
397                WDMUtils.setFibersNumFrequencySlots(netPlan , numFrequencySlotsPerFiber.getInt() , wdmLayer);
398                IntArrayList slots = new IntArrayList (); DoubleArrayList vals = new DoubleArrayList ();
399                IntArrayList slots2 = new IntArrayList (); DoubleArrayList vals2 = new DoubleArrayList ();
400                for (int p = 0; p < P ; p ++)
401                {
402                        slots.clear(); vals.clear();
403                        x_ps.viewRow(p).getNonZeros(slots , vals);
404                        if (cpl11 != null) 
405                        { 
406                                slots2.clear(); vals.clear(); x2_ps.viewRow(p).getNonZeros(slots2 , vals2);
407                                if (slots.size() != slots2.size()) throw new RuntimeException ("Bad");
408                        } 
409                        if (slots.size() == 0) continue;
410                        
411                        final Demand ipDemand = ipDemand_p.get(p);
412                        for (int cont = 0 ; cont < slots.size() ; cont ++)
413                        {
414                                final int s = slots.get (cont);
415                                final Demand newWDMDemand = netPlan.addDemand(ipDemand.getIngressNode() , ipDemand.getEgressNode() , 
416                                                lineRate_p.get(p) , RoutingType.SOURCE_ROUTING , null , wdmLayer);
417                                final Route r = WDMUtils.addLightpath(newWDMDemand , new WDMUtils.RSA(seqLinks_p.get(p) , s , numSlots_p.get(p) , regPositions_p.get(p)) , lineRate_p.get(p));
418                                final Link ipLink = newWDMDemand.coupleToNewLinkCreated(ipLayer);
419                                final double ipTrafficToCarry = Math.min(lineRate_p.get(p) , ipDemand.getBlockedTraffic());
420                                netPlan.addRoute(ipDemand , ipTrafficToCarry , ipTrafficToCarry , Arrays.asList(ipLink), null);
421                                if (cpl11 != null)
422                                {
423                                        final int s2 = slots2.get(cont);
424                                        final Route backupRoute = WDMUtils.addLightpath(newWDMDemand , new WDMUtils.RSA(seqLinks2_p.get(p) , s2 , numSlots_p.get(p) , regPositions2_p.get(p)) , 0);
425                                        r.addBackupRoute(backupRoute);
426                                }
427                        }
428                }
429                
430                WDMUtils.checkResourceAllocationClashing(netPlan,true,true,wdmLayer);
431
432                return "Ok!";
433        }
434
435        private static double getLengthInKm (Collection<Link> r) { double res = 0; for (Link e : r) res += e.getLengthInKm(); return res; }
436        
437        @Override
438        public String getDescription()
439        {
440                return "Algorithm based on an ILP solving the Routing, Spectrum, Modulation Assignment (RSMA) problem with regenerator placement, in flexi (elastic) or fixed grid optical WDM networks, with or without fault tolerance, latency and/or lightpath bidirectionality requisites (see the Javadoc for details).";
441        }
442
443        @Override
444        public List<Triple<String, String, String>> getParameters()
445        {
446                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
447                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
448        }
449}