Invited Session Tue.2.H 3002

Tuesday, 13:15 - 14:45 h, Room: H 3002

Cluster 23: Telecommunications & networks [...]

Tree problems


Chair: Ivana Ljubic



Tuesday, 13:15 - 13:40 h, Room: H 3002, Talk 1

Bernd Zey
The stochastic Steiner tree problem: Models and solution strategies

Coauthors: Immanuel Bomze, Markus Chimani, Michael Jünger, Ivana Ljubic, Petra Mutzel


We consider the Steiner tree problem under a two-stage stochastic model with fixed recourse and finitely many scenarios. Thereby, edges are bought in the first stage when only probabilistic information on future edge costs and the set of terminals is known. In the second stage, one scenario is realized and additional edges are purchased to connect the now known set of terminals. The goal is to buy profitable edges in the first stage such that the overall expected costs are minimized, i.e., the sum of the first and expected second stage costs.
We discuss the strength of undirected, semi-directed, and directed cut-set based integer programming models with binary first and second stage variables. To solve this NP-hard problem to optimality, we suggest a branch-and-cut approach based on Benders decomposition and the derived Integer-L-shaped algorithm. By a simple modification of the optimal dual solution of the subproblems we show how to improve the generated optimality Cuts which reduce the running time significantly. In our experiments we compare the extended formulation and the decomposition of the different models computationally.



Tuesday, 13:45 - 14:10 h, Room: H 3002, Talk 2

Pedro Moura
Generalized degree constraints arising in wireless networks problems

Coauthors: Luís Gouveia, Amaro de Sousa


We describe a minimum spanning tree problem with generalized degree constraints which arises in the design of wireless networks. In these networks, each link is implemented through a point-to-point wireless transmission system composed by a transmitter/receiver antenna and a signal processing unit at each side of the link. Each system works on different frequency channels chosen from a limited set of available channels. Possible overlapping may occur in a node, i.e., part of the transmitted signal on one channel is added as interference on the received signal on another channel. Due to propagation effects, the signal strength on the receiver side decreases as the distance to the transmitter side increases. Therefore, the maximum distance between antennas that allow the link to work properly, depends on the amount of interference introduced by all the frequency channels used on its end nodes
We consider different types of links that may be installed between two nodes depending on the distance between them and their degrees. We propose three models and compare the linear programming relaxations. We also test these models against a set of instances with up to 100 nodes.



Tuesday, 14:15 - 14:40 h, Room: H 3002, Talk 3

Subramanian Raghavan
Recoverable robust two level network design

Coauthors: Eduardo Alvarez Miranda, Ivana Ljubic, Paolo Toth


In this problem one of two available technologies can be installed on each edge and all customers of the network need to be served by at least the lower level (secondary) technology. We are confronted with uncertainty regarding the set of primary customers, i.e., the set of nodes that need to be served by the higher level (primary) technology. A set of discrete scenarios associated to the possible realizations of primary customers is available. The network is built in two stages. One may decide to install the primary technology on some of the edges in the first stage, or one can wait to see which scenario will be realized, in which case, edges with the installed secondary technology may be upgraded to primary technology, but at higher recovery cost. The goal is to build a spanning tree in the first stage that serves all customers by at least the lower level technology, and minimizes the first stage installation cost plus the worst-case cost needed to upgrade the edges of that tree, so that the primary customers of each scenario can be served using the primary technology. We study the complexity of the problem on trees and provide MIP models and a branch-and-cut approach.


  The best way to go for you to know the credible Payday Loans Michigan providers. But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.