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


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.


Talk 3 of the invited session Tue.2.H 3002
"Tree problems" [...]
Cluster 23
"Telecommunications & networks" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.