Combinatorial Optimization & Graph Algorithms

Efficient Algorithms for Path-Based and Dynamic Flow Problems in Large Networks

Participants:	Nadine Baumann, Ekkehard Köhler, Rolf H. Möhring, Heiko Schilling, Martin Skutella
Supported by:	within the research program "Algorithmik großer und komplexer Netzwerke" (DFG-Schwerpunkt Nr. 1126)
Cooperation with:

Efficient algorithms are of crucial importance for a variety of network-based applications like traffic management and planning, telecommunications, and data traffic in the Internet. A typical example of such applications is the minimization of network load by simultaniously satisfying various user constraints. This naturally leads to optimization problems in networks, which are usually treated with standard techniques from network optimization, such as algorithms for shortest paths, maximum flows, min-cost multi-commodity flows. To cope with the various user constraints that often relate to the quality of the flow-carrying paths in the given solution, path-based formulations for different flow problems are of interest. While the classical techniques for solving flow problems are efficient for common networks of smaller size and complexity, they often ignore substantial aspects that are characteristic of larger, more complex networks. Due to their input size, large and complex networks can generally not be supplied explicitly but instead have to be given in some implicit manner. For example, a traffic network can be modelled via a hierarchical structure where different street classes (local streets, highways, etc.) define different levels of hierarchy. Unfortunately, standard algorithms for network optimization are generally not capable of using this condensed representation of the networks but require the full expanded network.

In this project we want to develop and test algorithms for solving "path-based" flow and multi-commodity flow problems on large and complex networks. The theoretical challenges here are two-fold. First, the algorithms must be able to solve problems using only partial information about the network structure, since it is given implicitly. Second, the constraints of our problems call for new path-based algorithmic approaches in order to solve flow problems that are tailored for our large networks. The practical test bed for these algorithms are traffic routing problems, on which we cooperate with DaimlerChrysler. For these applications, practical data is available for testing the developed algorithms.

Jahres-Kolloquium_2002_talk_1on1.pdf
Jahres-Kolloquium_2002_talk_2on1.pdf