[Zurück]

A Chwatal, N. Musil, G. Raidl:
"Solving a multi-constrained network design problem by lagrangean decomposition and column generation";
Vortrag: International Network Optimization Conference (INOC), Pisa; 26.04.2009 - 29.04.2009; in: "Proceedings of the International Network Optimization Conference 2009", (2009), 7 S.

In this paper we describe two approaches to solve a real-world multi-constrained network-design
problem. The objective is to select the cheapest subset of links in a given network which enables to
feasibly route messages from respective source to target nodes regarding various constraints. These
constraints include particular capacity and delay constraints for each message, as well as a global
delay constraint. Furthermore some messages may only be routed on connections supporting a secure
protocol. The problem is strongly NP-hard and larger instances cannot be solved to provable opti-
mality in practice. Hence, we present two heuristic approaches based on Lagrangean Decomposition
and Column Generation, which turned out to be well suited. From these methods we obtain lower
bounds as well as feasible solutions.

http://publik.tuwien.ac.at/files/PubDat_176380.pdf