[Back]

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.