Ziegelmann, Mark

Constrained Shortest Paths and Related Problems

The classical shortest path problem, to find a path
of minimal cost between two nodes in a graph, is efficiently solvable
in polynomial time. However, in many applications we also have additional
budget or resource constraints on a path. This problem is known as
constrained shortest path problem and unfortunately belongs to the
class of ``hard''
problems for which no polynomial time algorithm is known.
In this thesis, we propose a 2-step method for the constrained shortest
path problem. We first solve
a relaxation to get upper and lower bounds and then close the gap with
clever path ranking to
obtain the exact solution. We compare different old and new methods
both theoretically and experimentally.
The 2-step method also works for a more general class of
constrained network optimization problems. We illustrate the
generic approach using several examples. We have also developed
a software package {\sc Cnop} that provides this generic 2-step
approach as well as all state of the art algorithms for
constrained shortest paths.