N. Musil:

"Design eines sicherheits-, zeit- und kostenkritischen Kommunikationsnetzwerkes mittels Lagrange Relaxierung und Spaltengenerierung";

Supervisor: G. Raidl, A Chwatal; Institut für Computergraphik und Algorithmen, 2008; final examination: 2008-12.

E cient network routing is becoming more and more important { examples

are internet telephony or event-based message systems. The particular

problem emerged from the industry cooperation SWIS in the context safetycritical

communication of air tra c management. In this thesis the design of

a network is optimized for design and protocol costs. The goal is to nd a minimum

cost network enabling the simultaneous routing of multiple messages.

Capacity constraints for each edge, delay constraints for individual messages,

as well as a global delay, and security constraints make the optimization

di cult.

In this thesis several algorithmic approaches for solving this NP-hard

problem are discussed. An Integer Linear Programming based approach using

a multi-commodity

ow formulation enables to solve small problem instances

to provable optimality.

To simplify the problem constraints are brought into the objective function

by attaching Lagrangean multipliers to them. This approach is called

Lagrangean relaxation. This yields independent subproblems for each transport.

In an iterative process the coe cients of the Lagrange multipliers are

systematically adapted and lower bounds for the original problem are obtained.

Heuristics can be used to derive valid solutions.

Based on an alternative formulation, which introduces a variable for each

possible path, the problem is solved by Column Generation. Starting from

a valid solution, further improving variables are iteratively added. These

variables can be found by solving the same subproblem as for Lagrangean

relaxation.

By the presented algorithms small instances can be solved within a few

minutes to optimality. For larger instances good heuristic solutions can be

found. Tight lower bounds obtained by Lagrangean relaxation enable to measure

the quality of heuristic solutions. Based on extensive experimental tests,

pros and cons of each approach are discussed in this thesis.

Created from the Publication Database of the Vienna University of Technology.