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