| 1. |
- Henningsson, Mathias, 1970-, et al.
(författare)
-
A ring generation problem based on the traveling salesman subtour problem
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Survivability and high redundancy are two critical issues in field of telecommunications. If a telecommunication network is built up by rings, high redundancy can be established, since the traffic can be sent in either direction. Traffic is usually sent using one direction, and if a failure occurs, the opposite direction is used. There is often a number of requirements on a ring, such as a limit on the number of connected nodes. This means that the network will include a number of rings, and traffic between rings must be possible. Therefore, a network must include a number of transit nodes, where it is possible to send traffic between the rings. We focus on the case where network includes two transit nodes and each ring must include at least one transit node. Since the number of rings is enormous one needs to generate rings.This paper discusses how to generate new rings, given that each node has a reward for connecting the node to the ring. The problem that occurs is a modification of a traveling salesman subtour problem with a additional constraint on the number of nodes connected. A problem formulation is given and some solution approaches are suggested. Two different scenarios are discussed, one where the aim is to modify an already existing ring, and one where the aim is to build a complete new ring. Some computational results are given for a real data network.
|
|
| 2. |
- Henningsson, Mathias, 1970-, et al.
(författare)
-
A ring network design problem and heuristics for generating a set of feasible rings
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We discuss the problem of designing a telecommunication network with the survivability requirement that the network should be composed of connected rings of links. The work design problem is then to choose links from a given network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. The traffic between rings may pass through other rings. Each ring is associated with a certain fixed cost depending on the length of the ring. We describe the problem, modeled as a linear integer programming problem. We find a feasible solution to the problem by first find good rings in the network using two heuristics, and then solve the optimization model using only these rings. Finally, we give some computational results for different networks.
|
|
| 3. |
- Henningsson, Mathias, 1970-, et al.
(författare)
-
A ring network design problem solved by a ring generation and allocation approach
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The development of optical fibers in telecommunications has lead large changes in the field. When design a telecommunication network, capacity nowadays is cheap, and the minimal cost design tends to be a tree. Since such a design is very vulnerable for link or node failures, one often wish to include some kind of survivability requirement, for example that the network should be two-edge-connected or two-node-connected. Another form of design model is to prescribe that the network should be composed of connected rings of links. The network design problem is then to choose links from a give network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. Each possible ring is associated with a certain fixed cost, and all links in a certain ring are given the same capacity. Traffic between rings may pass through other rings, which is an important element of the problem. Finally, reserve capacity allocation according to certain principles is included. We describe the problem, modeled as a linear integer programming problem, and discuss different formulations and different solution methods. As the problem is quite difficult, we focus on heuristic solution methods, including elements of column generation and Lagrangean relaxation.
|
|
| 4. |
- Henningsson, Mathias, 1970-, et al.
(författare)
-
Calculating cost coefficients for generation of rings in network design
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We discuss a telecommunication network problem where the aim is to design a network that should be composed of connected rings of links. Each possible ring is associated with a certain fixed cost. The traffic between rings may pass through other rings, where the switch between two rings must be done at certain transit nodes. Each ring must pass at least one transit node. We describe the problem, modeled as a linear integer programming problem. We focus on calculating cost coefficients for ring generation using Lagrangean relaxation.
|
|
| 5. |
- Henningsson, Mathias, 1970-, et al.
(författare)
-
Lagrangean price directive ring generation for network design
- 2003
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- This paper addresses the problem of designing a telecommunication network with certain survivability requirements, namely that the network should be made up between connected rigs. This way single link failures do not kill the connection between any two nodes. One can make the network two-node-connected by including two specific nodes in all rings. This gives rise to a network design optimization problem with fixed costs on rings. In this paper we describe a solution approach for such problems, based on generation of rings. The approach is in principle a column generation technique, where the dual prices used for pricing out columns are obtained with the help of Lagrange duality, instead of the usual LP-duality. Computational tests are reported.
|
|
