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.DoubleMatrix1D;
024import cern.colt.matrix.tdouble.DoubleMatrix2D;
025
026import com.jom.OptimizationProblem;
027import com.net2plan.interfaces.networkDesign.IAlgorithm;
028import com.net2plan.interfaces.networkDesign.Net2PlanException;
029import com.net2plan.interfaces.networkDesign.NetPlan;
030import com.net2plan.interfaces.networkDesign.Node;
031import com.net2plan.utils.InputParameter;
032import com.net2plan.utils.Triple;
033
034/**
035 * This algorithm gives access to several variants of full topology design problems. 
036 * @net2plan.description 
037 * @net2plan.keywords Topology assignment (TA), Capacity assignment (CA), Flow assignment (FA), Flow-link formulation, JOM
038 * @net2plan.ocnbooksections Section 7.3
039 * @net2plan.inputParameters 
040 * @author Pablo Pavon-Marino
041 */
042public class Offline_tcfa_xdeFormulationsMinLinkCost implements IAlgorithm
043{
044        private InputParameter topologyType = new InputParameter ("topologyType", "#select# arbitrary-mesh bidirectional-mesh unidirectional-ring bidirectional-ring bidirectional-tree", "The constraints on the link topology: arbitrary topology (no specific constraint), arbitrary bidirectional topology (link from i to j exists iff it exists from j to i), unidirectional ring, bidirectional ring, bidirectional tree");
045        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");
046        private InputParameter solverLibraryName = new InputParameter ("solverLibraryName", "", "The solver library full or relative path, to be used by JOM. Leave blank to use JOM default.");
047        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)");
048        private InputParameter fixedCostFactorPerKm = new InputParameter ("fixedCostFactorPerKm", (double) 1.0 , "Fixed cost factor per km of a link (the cost of a link of d km and 0 capacity is d times this quantity)" , 0 , true , Double.MAX_VALUE , true);
049        private InputParameter linkPropagationSpeedInKmPerSecond = new InputParameter ("linkPropagationSpeedInKmPerSecond", (double) 200000 , "The propagation speed in km per second of the deployed links" , 0 , false , Double.MAX_VALUE , true);
050        private InputParameter U_max = new InputParameter ("U_max", (double) -1 , "The maximum capacity a link can have. If non positive, there is not limit");
051        private InputParameter variableCostFactorPerKmAndTrafficUnit = new InputParameter ("variableCostFactorPerKmAndTrafficUnit", (double) 1 , "Variable cost factor per km and traffic unit of a link (the cost of a link of 1 km and 1 unit of capacity, and 0 of fixed cost)" , 0 , true , Double.MAX_VALUE , true);
052        
053        @Override
054        public String executeAlgorithm(NetPlan netPlan, Map<String, String> algorithmParameters, Map<String, String> net2planParameters)
055        {
056                /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */
057                InputParameter.initializeAllInputParameterFieldsOfObject(this, algorithmParameters);
058
059                /* Basic checks */
060                final int N = netPlan.getNumberOfNodes();
061                final int D = netPlan.getNumberOfDemands();
062                if (N == 0 || D == 0) throw new Net2PlanException("This algorithm requires a topology and a demand set");
063                
064                /* Initialize some variables */
065                final double PRECISION_FACTOR = Double.parseDouble(net2planParameters.get("precisionFactor"));
066
067                /* Create a full mesh of links in the netPlan object */
068                netPlan.removeAllLinks();
069                for (Node i : netPlan.getNodes ()) for (Node j : netPlan.getNodes ()) if (i.getId () > j.getId ()) netPlan.addLinkBidirectional(i, j, 1.0 , netPlan.getNodePairEuclideanDistance(i, j), linkPropagationSpeedInKmPerSecond.getDouble() , null);
070                                        
071                /* Compute the distances of the potential links */
072                final int E_fm = netPlan.getNumberOfLinks();
073                final DoubleMatrix1D d_e = netPlan.getVectorLinkLengthInKm();
074                final DoubleMatrix1D h_d = netPlan.getVectorDemandOfferedTraffic();
075                final DoubleMatrix2D Abid_ee = netPlan.getMatrixLink2LinkBidirectionalityMatrix ();
076
077                /* Create the optimization problem object (JOM library) */
078                OptimizationProblem op = new OptimizationProblem();
079
080                /* Set some input parameters */
081                op.setInputParameter("U_max", U_max.getDouble() > 0? U_max.getDouble() : h_d.zSum());
082                op.setInputParameter("fc", fixedCostFactorPerKm.getDouble());
083                op.setInputParameter("vc", variableCostFactorPerKmAndTrafficUnit.getDouble());
084                op.setInputParameter("h_d", h_d, "row");
085                op.setInputParameter("d_e", d_e, "row");
086                op.setInputParameter("A_ne", netPlan.getMatrixNodeLinkIncidence());
087                op.setInputParameter("A_nd", netPlan.getMatrixNodeDemandIncidence());
088
089                /* Add the decision variables to the problem */
090                op.addDecisionVariable("z_e", true, new int[] { 1, E_fm }, 0, 1); /* 1 if there is a link installed in the candidate link e */
091                op.addDecisionVariable("u_e", false, new int[] { 1, E_fm }, 0, U_max.getDouble() <= 0? Double.MAX_VALUE : U_max.getDouble()); /* the capacity installed in the candidate  link e, if any */
092                op.addDecisionVariable("xx_de", false, new int[] { D, E_fm }, 0, 1); /* fraction of the traffic of demand d, that is carried in the candidate link e */
093                
094                /* Sets the objective function */
095                op.setObjectiveFunction("minimize", "sum(fc * d_e .* z_e) + sum (vc * d_e .* u_e)");
096
097                /* Compute some matrices required for writing the constraints */
098                op.addConstraint("A_ne * (xx_de') == A_nd"); /* the flow-conservation constraints (NxD constraints) */
099                op.addConstraint("h_d * xx_de <= u_e"); /* the capacity constraints (E constraints) */
100                op.addConstraint("u_e <= U_max * z_e"); /* limit to maximum link capacity */
101                
102                if (topologyType.getString().equalsIgnoreCase("arbitrary-mesh"))
103                {
104                }
105                else if (topologyType.getString().equalsIgnoreCase("bidirectional-mesh"))
106                { 
107                        op.setInputParameter("Abid_ee", Abid_ee); 
108                        op.addConstraint("z_e == z_e * Abid_ee"); /* If a link exists, also the opposite */
109                } 
110                else if (topologyType.getString().equalsIgnoreCase("unidirectional-ring"))
111                {
112                        op.setInputParameter("Aout_ne" , netPlan.getMatrixNodeLinkOutgoingIncidence());
113                        op.setInputParameter("Ain_ne" , netPlan.getMatrixNodeLinkIncomingIncidence());
114                        op.addConstraint("Aout_ne * z_e' == 1"); /* number of out links of a node is one */
115                        op.addConstraint("Ain_ne * z_e' == 1"); /* number of in links of a node is one */
116                }
117                else if (topologyType.getString().equalsIgnoreCase("bidirectional-ring"))
118                {
119                        op.setInputParameter("Aout_ne" , netPlan.getMatrixNodeLinkOutgoingIncidence());
120                        op.setInputParameter("Ain_ne" , netPlan.getMatrixNodeLinkIncomingIncidence());
121                        op.setInputParameter("Abid_ee", Abid_ee); 
122                        op.addConstraint("z_e == z_e * Abid_ee"); /* If a link exists, also teh opposite */
123                        op.addConstraint("Aout_ne * z_e' == 2"); /* number of out links of a node is two */
124                        op.addConstraint("Ain_ne * z_e' == 2"); /* number of in links of a node is two */
125                }
126                else if (topologyType.getString().equalsIgnoreCase("bidirectional-tree"))
127                {
128                        op.setInputParameter("Abid_ee", Abid_ee); 
129                        op.addConstraint("z_e == z_e * Abid_ee"); /* If a link exists, also teh opposite */
130                        op.addConstraint("sum(z_e) == " + (2*(N-1))); /* the number of links is characteristic of a tree */
131                        System.out.println ("num links: " + 2*(N-1));
132                }
133                else throw new Net2PlanException ("Unknown topology type " + topologyType.getString());
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                final DoubleMatrix1D z_e = op.getPrimalSolution("z_e").view1D().copy ();
144                final DoubleMatrix1D u_e = op.getPrimalSolution("u_e").view1D().copy ();
145                final DoubleMatrix2D xx_de = op.getPrimalSolution("xx_de").view2D().copy ();
146
147                /* Sets the routing, capacities and links. Remove unused links (no capacity) */
148                netPlan.setRoutingFromDemandLinkCarriedTraffic(xx_de , true , true);
149                netPlan.setVectorLinkCapacity(u_e);
150                netPlan.removeAllLinksUnused (PRECISION_FACTOR);
151                
152                return "Ok! Num links: " + netPlan.getNumberOfLinks() + ", total capacity: " + u_e.zSum();
153        }
154
155        @Override
156        public String getDescription()
157        {
158                return "This algorithm gives access to several variants of full topology design problems. Given a set of nodes and a set of unicast demands with known  offered traffic. The algorithm searches for (i) the set of links to deploy, (ii) the link capacities, and (iii) how the traffic is routed over the links. The objective function consists in minimizing the cost, given by the sum of the link costs. The cost of a link is the sum of a fixed cost (proportional to the link length) that applies if the link exists (whatever its capacity is), and a variable cost proportional to its capacity and distance. Different problem variants can be selected, with different constraints (e.g. constraint the topology to be bidirectional, to be a ring, a tree...). The solution is searched by solving several variants of flow-link formulations.";
159        }
160
161        @Override
162        public List<Triple<String, String, String>> getParameters()
163        {
164                /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */
165                return InputParameter.getInformationAllInputParameterFieldsOfObject(this);
166        }
167}