Examples involving 'Topology assignment (TA)'

This algorithm computes the bidirectional ring which minimizes the total ring length, using an ACO (Ant Colony Optimization) heuristic, described as Ant System in the literature

Keywords: Ant Colony Optimization (ACO), Capacity assignment (CA), Topology assignment (TA)

This algorithm computes the bidirectional ring which minimizes the total ring length, using an ACO (Ant Colony Optimization) heuristic, described as Ant System in the literature: M. Dorigo, V. Maniezzo, A. Colorni, "Ant system: optimization by a colony of cooperating agents", IEEE T on Cybernetics, 1996. The cost of a link equals the euclidean distance between link end nodes. The algorithm executes ACO iterations until the maxExecTime is reached. In each ACO iteration, a loop for each ant is executed. Each ant, creates a greedy-randomized solution using the pheromones information of each potential link, and each link length, as follows. Each ant starts in a node chosen randomly. At each iteration, an ant in node n decides the next node to visit randomly among the non-visited nodes, being the probability of choosing node n' proportional to ph_nn'^alpha b_nn'^beta. ph_nn' is the amount of pheromones associated to link nn', b_nn' is the inverse of the distance between both nodes. alpha and beta are parameters tuning the importance of pheromones and link distances respectively. After all ants have finished, an evaporation strategy is executed, where each link nn' looses pheromones multiplicatively (pheromones are multiplied by 1-r, where r is a 0...1 evaporation factor). After evaporation phase, a reinforcement step is completed, where each ant a adds a quantity 1/La to the pheromones of all links traversed, being La the total distance of its ring.

This algorithm computes the bidirectional ring which minimizes the total ring length, using a GRASP heuristic.

Keywords: Capacity assignment (CA), Greedy-Randomized Adaptive Search Procedure (GRASP), Topology assignment (TA)

This algorithm computes the bidirectional ring which minimizes the total ring length, using a GRASP heuristic. The cost of a link equals the euclidean distance between link end nodes. The algorithm executes GRASP iterations until the maxExecTime is reached. In each GRASP iteration, a solution is first created using a greedy-randomized approach. Then, this solution is the starting point of a local search (first-fit) heuristic, where two rings are considered neighbors when they have all but 2 bidirectional links in common. The greedy randomized approach is based on the concept of restricted candidate list (RCL). The ring starts with one single node chosen randomly. In each greedy iteration one node is added to the ring, randomly chosen from a RCL created in this iteration. The RCL contains the non-visited nodes which are closer to current node. In particular, the nodes in the RCL are those which are at a distance from c_min to c_min + alpha * (c_max - c_min). c_min and c_max are the distances from last added node, to closest and furthest non-visited nodes. alpha is an algroithm parameter between 0 and 1, tuning the size of the RCL. When alpha=0, the algorithm is equal to pure greedy nearest neighbor heuristic. If alpha = 1, randomness is maximum: a non-visited node is chosen randomly.

Compute a minimum cost access-to-core network

Keywords: Capacity assignment (CA), Local search (LS) heuristic, Topology assignment (TA)

Given a set of access nodes, this algorithm computes the subset of access nodes which have a core node located next to it (in the same place), and the links access-to-core nodes, so that the network cost is minimized. This cost is given by a cost per core node (always 1) plus a cost per link, given by the product of link distance and the user-defined parameter linkCostPerKm. Access-core link capacities are fixed to the user-defined parameter linkCapacities. This problem is solved using a local-search heuristic.

Computes the optimal bidirectional ring for the network

Keywords: Capacity assignment (CA), JOM, MILP formulation, Topology assignment (TA)

Given a set of nodes \( N \), this algorithm computes the bidirectional ring with the minimum length (in km) in all its nodes, solving with an ILP (Integer Linear Program) the associated Traveling Salesman Problem (TSP) instance. All the links are set to have the capacity passed as input parameter.

Computes a bidirectional ring for the network using a nearest-neighbor heuristic

Keywords: Capacity assignment (CA), Greedy heuristic, Topology assignment (TA)

Given a set of nodes, this heuristic tries to find a (possibly sub-optimal) minimum cost bidirectional ring (where the cost of a link is given by its length in km) using the nearest-neighbor greedy heuristic.

Computes the optimal minimum cost access-to-core network

Keywords: Capacity assignment (CA), JOM, MILP formulation, Topology assignment (TA)

Given a set of access nodes, this algorithm computes the subset of access nodes which have a core node located next to it (in the same place), and the links access-to-core nodes, so that the network cost is minimized. This cost is given by a cost per core node (always 1) plus a cost per link, given by the product of link distance and the user-defined parameter linkCostPerKm. Access-core link capacities are fixed to the user-defined parameter linkCapacities. A core node cannot be connected to more than K_max access nodes, a user-defined parameter. This problem is modeled as a ILP and optimally solved using a solver.

Compute the bidirectional minimum spanning tree for the network

Keywords: Capacity assignment (CA), Topology assignment (TA)

This algorithm computes the bidirectional minimum spanning tree (MST) for the given set of nodes, using the node distance as the cost measure for each link.

For a network of \(N\) nodes, the returned topology is a tree of \(N-1\) bidirectional links, so that no other topology is able to connect the \(N\) nodes with bidirectional links, at a lower cost (being the cost the sum of the lengths of the links). To compute the MST, the Prim algorithm is implemented.

Waxman generator

Keywords: Capacity assignment (CA), Topology assignment (TA)

Generates a topology using the Waxman random model

Computes a minimum cost network with optimized capacities and traffic routing, path-link formulation

Keywords: Capacity assignment (CA), Flow assignment (FA), JOM, MILP formulation, Topology assignment (TA)

Given a set of nodes \( N \), and a traffic demand, this algorithm computes the set of links, their capacities and the routing of traffic that optimally minimizes the network cost given by a fixed cost per link, plus a variable cost with link capacities. Between two nodes, at most one link can exist. The maximum link capacity is U_max, a user-defined parameter. Link fixed cost is given by link distance by fixedCostFactorPerKm, a user-defined parameter. Link variable cost is given by link distance, by link capacity, by variableCostFactorPerKmAndTrafficUnit, a user-defined parameter. The problem is modeled with JOM as a MILP, and optimally solved by a external solver.