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
020
021package com.net2plan.examples.ocnbook.offline;
022
023import cern.colt.list.tdouble.DoubleArrayList;
024import cern.colt.list.tint.IntArrayList;
025import cern.colt.matrix.tdouble.DoubleFactory1D;
026import cern.colt.matrix.tdouble.DoubleMatrix1D;
027import cern.colt.matrix.tdouble.DoubleMatrix2D;
028import cern.colt.matrix.tdouble.DoubleMatrix3D;
029import com.jom.DoubleMatrixND;
030import com.jom.OptimizationProblem;
031import com.net2plan.interfaces.networkDesign.*;
032import com.net2plan.utils.Constants.RoutingType;
033import com.net2plan.utils.InputParameter;
034import com.net2plan.utils.Triple;
035
036import java.util.List;
037import java.util.Map;
038
039/**
040 * Solves several variants of unicast routing problems with flow-link formulations, so that designs are fault tolerant to a set of failure states, using shared restoration
041 * @net2plan.description
042 * @net2plan.keywords JOM, Flow-link formulation, Flow assignment (FA), Network recovery: restoration
043 * @net2plan.ocnbooksections Section 4.3, Section 4.6.7
044 * @net2plan.inputParameters 
045 * @author Pablo Pavon-Marino
046 */
047public class Offline_fa_xdeSharedRestoration implements IAlgorithm
048{
049        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");
050        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");
051        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
052        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)");
053
054        @Override
055        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
056        {
057                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
058                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
059                if (netPlan.getNumberOfSRGs() == 0) throw new Net2PlanException("No SRG was defined"); 
060
061                /* Basic checks */
062                final int N = netPlan.getNumberOfNodes();
063                final int E = netPlan.getNumberOfLinks();
064                final int D = netPlan.getNumberOfDemands();
065                final int S = netPlan.getNumberOfSRGs();
066                if (N == 0 || D == 0 || E == 0) throw new Net2PlanException("This algorithm requires a topology with links, and a demand set");
067
068                /* Remove all unicast routed traffic. Any multicast routed traffic is kept */
069                netPlan.removeAllUnicastRoutingInformation();
070                netPlan.setRoutingTypeAllDemands(RoutingType.SOURCE_ROUTING);
071                
072                /* Initialize some variables */
073                DoubleMatrix1D u_e = netPlan.getVectorLinkSpareCapacity(); // just the unused capacity (some capacity may be used by multicast traffic)
074                DoubleMatrix1D h_d = netPlan.getVectorDemandOfferedTraffic();
075                
076                /* Create the optimization problem object (JOM library) */
077                OptimizationProblem op = new OptimizationProblem();
078                op.setInputParameter("E", E);
079                op.setInputParameter("u_e", u_e, "row");
080                op.setInputParameter("h_d", h_d, "row");
081                op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence());
082                op.setInputParameter("onesS", DoubleFactory1D.dense.make (S , 1.0) , "row");
083                op.setInputParameter("A_nd", netPlan.getMatrixNodeDemandIncidence());
084                op.setInputParameter("A_es", netPlan.getMatrixLink2SRGAssignment());
085                DoubleMatrixND A_des = new DoubleMatrixND (new int []{D,E,S} , "sparse"); for (SharedRiskGroup srg : netPlan.getSRGs()) for (Link e : srg.getAffectedLinksAllLayers()) for (int d = 0; d < D ; d ++) A_des.set(new int [] {d,e.getIndex (),srg.getIndex()} , 1.0);
086                DoubleMatrixND A_nds = new DoubleMatrixND (new int []{N,D,S} , "sparse"); for (Demand d : netPlan.getDemands()) for (int s = 0; s < S ; s ++) { A_nds.set(new int [] {d.getIngressNode().getIndex(),d.getIndex(),s}, 1.0); A_nds.set(new int [] {d.getEgressNode().getIndex(),d.getIndex(),s}, -1.0); }
087                op.setInputParameter("A_des", A_des);
088                op.setInputParameter("A_nds", A_nds);
089                
090                /* Add the decision variables to the problem */
091                op.addDecisionVariable("xx_de", true, new int[] { D, E }, 0, 1); /* 1 if the primary path of demand d, traverses link e */
092                op.addDecisionVariable("xx_des", true, new int[] { D, E , S }, 0, 1); /* 1 if the primary path of demand d, traverses link e */
093
094                /* Sets the objective function */
095                if (optimizationTarget.getString ().equalsIgnoreCase("min-av-num-hops"))
096                {
097                        op.setObjectiveFunction("minimize", "sum (h_d * xx_de)");
098                        op.addConstraint("h_d * xx_de <= u_e"); /* the capacity constraints in the no-failure state */
099                        op.addConstraint("sum (diag(h_d) * xx_des , 1) <=  u_e' * onesS"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */
100                }
101                else if (optimizationTarget.getString ().equalsIgnoreCase("minimax-link-utilization"))
102                {
103                        op.setInputParameter ("EPSILON" , 1e-4);
104                        op.addDecisionVariable("rho", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link in any failure state */
105                        op.setObjectiveFunction("minimize", "rho + EPSILON * sum(xx_de) + EPSILON * sum(xx_des) ");
106                        op.addConstraint("h_d * xx_de <= rho * u_e"); /* the capacity constraints in the no-failure state */
107                        op.addConstraint("sum (diag(h_d) * xx_des , 1) <=  rho * u_e' * onesS"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */
108                }
109                else if (optimizationTarget.getString ().equalsIgnoreCase("maximin-link-idle-capacity"))
110                {
111                        op.setInputParameter ("EPSILON" , 1e-4);
112                        op.addDecisionVariable("u", false, new int[] { 1, 1 }, 0, Double.MAX_VALUE); /* idle capacity in the bottleneck link */
113                        op.setObjectiveFunction("maximize", "u - EPSILON * sum(xx_de) - EPSILON * sum(xx_des)");
114                        op.addConstraint("h_d * xx_de <= -u + u_e"); /* the capacity constraints in the no-failure state */
115                        op.addConstraint("sum (diag(h_d) * xx_des , 1) <=  -u + u_e' * onesS"); /* the capacity constraints summing primary and backup paths (E constraints), make that rho becomes the worse case link utilization */
116                }
117                else throw new Net2PlanException ("Unknown optimization target " + optimizationTarget.getString());
118                
119                /* Add constraints */
120                op.addConstraint("A_ne * xx_de' == A_nd"); /* flow conservation constraints for the non-failure state */
121                op.addConstraint("A_ne * permute(xx_des,[2;1;3]) == A_nds"); /* flow conservation constraints in all the failure states */
122                op.addConstraint("xx_des <= 1 - A_des"); /* failing links do not carry traffic */
123
124                DoubleMatrixND I_sse = new DoubleMatrixND (new int [] {S,S,E}); 
125                DoubleMatrixND I_ees = new DoubleMatrixND (new int [] {E,E,S}); 
126                for (int e = 0 ; e < E ; e ++) for (int s = 0 ; s < S ; s ++) { I_sse.set (new int [] { s,s,e } ,1.0); I_ees.set (new int [] { e,e,s } ,1.0); }
127                op.setInputParameter("I_sse" , I_sse);
128                op.setInputParameter("I_ees" , I_ees);
129                op.setInputParameter("onesE" , DoubleFactory1D.dense.make(E,1) , "row");
130
131                /* If a demand does not traverse a changing link in failure state s, keep the same routing as in no-failure state */
132                op.addConstraint("- permute((xx_de * A_es) * I_sse , [1;3;2]) <= xx_des - xx_de * I_ees "); 
133                op.addConstraint("  permute((xx_de * A_es) * I_sse , [1;3;2]) >= xx_des - xx_de * I_ees "); 
134
135                /* Call the solver to solve the problem */
136                op.solve(solverName.getString (), "solverLibraryName", solverLibraryName.getString () , "maxSolverTimeInSeconds" , maxSolverTimeInSeconds.getDouble ());
137
138                /* If no solution is found, quit */
139                if (op.feasibleSolutionDoesNotExist()) throw new Net2PlanException("The problem has no feasible solution");
140                if (!op.solutionIsFeasible()) throw new Net2PlanException("A feasible solution was not found");
141
142                /* Retrieve the optimum solutions */
143                DoubleMatrix2D xx_de = op.getPrimalSolution("xx_de").view2D();
144                DoubleMatrix3D xx_des = op.getPrimalSolution("xx_des").view3D("sparse");
145
146                netPlan.setRoutingFromDemandLinkCarriedTraffic(xx_de , true , false , null);
147
148                checkSolution(netPlan, xx_de , xx_des);
149
150                return "Ok!";
151        }
152
153        @Override
154        public String getDescription()
155        {
156                return "Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains a link-disjoint or a SRG-disjoint (depending on user's choice) primary and backup path for the traffic of each demand, that minimizes the network congestion, with the constraint of non-bifurcated routing. For that it solves an ILP flow-link formulation (more complex in the SRG-disjoint case). In this algorithm, congestion is minimized by maximizing the idle link capacity in the bottleneck (the link with less idle capacity).";
157        }
158
159        @Override
160        public List<Triple<String, String, String>> getParameters()
161        {
162                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
163                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
164        }
165        
166        private static void checkSolution(NetPlan netPlan, DoubleMatrix2D xx_de , DoubleMatrix3D xx_des)
167        {
168                if (!netPlan.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated)");
169                if (!netPlan.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated)");
170
171                for (SharedRiskGroup srg : netPlan.getSRGs())
172                {
173                        NetPlan npThis = netPlan.copy ();
174                        npThis.removeAllUnicastRoutingInformation();
175                        DoubleMatrix2D this_xxde = xx_des.viewColumn (srg.getIndex ()).copy ();
176                        for (Link e : srg.getAffectedLinksAllLayers()) if (this_xxde.viewColumn(e.getIndex ()).zSum () != 0) throw new Net2PlanException("Bad - some failing links carry traffic");
177                        npThis.setRoutingFromDemandLinkCarriedTraffic(this_xxde , true , false , null);
178                        if (!npThis.getLinksOversubscribed().isEmpty()) throw new Net2PlanException("Bad - Some link is oversubscribed (constraint violated) in a failure");
179                        if (!npThis.getDemandsBlocked().isEmpty()) throw new Net2PlanException("Bad - Some demand is blocked (constraint violated) in a failure");
180                        for (Demand d : netPlan.getDemands ())
181                        {
182                                IntArrayList es_noFailure = new IntArrayList (); xx_de.viewRow (d.getIndex ()).getNonZeros(es_noFailure , new DoubleArrayList ());
183                                boolean affectedByThisFailure = false; for (Link e : srg.getAffectedLinksAllLayers()) if (xx_de.get(d.getIndex() , e.getIndex ()) != 0) { affectedByThisFailure = true; break; }
184                                if (!affectedByThisFailure)
185                                {
186                                        IntArrayList es_thisFailure = new IntArrayList (); this_xxde.viewRow (d.getIndex ()).getNonZeros(es_thisFailure , new DoubleArrayList ());
187                                        if (!es_noFailure.equals(es_thisFailure)) throw new Net2PlanException("Routing cannot change when a demand is not affected by the failure");
188                                }
189                        }
190                }
191        }
192}
193