3e cycle romand de Recherche Opérationnelle

March 3-7, 2001, Hotel de l'Europe, Zinal (VS), Switzerland

Spring seminar / Séminaire de printemps

Information and registration : http://rosowww.epfl.ch/3emecycle or alain.prodon@epfl.ch

Registration's deadline : January 31, 2002

Invited lecturers :

Alexander Schrijver, CWI, Amsterdam (NL)
Discrete Optimization : Theory and Applications

Kurt Mehlhorn, Max-Planck-Institut für Informatik, Saarbrücken (D)
Inside LEDA

Talk Abstracts :

Discrete Optimization : Theory and Applications
Alexander Schrijver

MINIMIZING A SUBMODULAR FUNCTION

Submodular functions arise in a natural way in network and matroid theory. In particular, the problem of finding the minimum value of a submodular function shows up in various combinatorial settings.

With the ellipsoid method it was shown by Grötschel, Lovasz and Schrijver (1981,1988) that the minimum value of a submodular function f can be found in strongly polynomial time, if f is given by an oracle returning f(U) for any given subset U. In 1999, two combinatorial strongly polynomial-time algorithms were found, one by Iwata, Fleischer, and Fujishige, and one by the lecturer.

We give an introduction to submodular functions and to the algorithms and we discuss some applications.

OPTIMIZATION AT DUTCH RAIL

For NS (Nederlandse Spoorwegen = Dutch Rail) we made algorithms to optimize railway stock routing and to determine the timetable. Both algorithms use graph theory and integer programming.

The routing algorithm concerns the circulation of different types of train units, which can be linked together. It can be described as a multicommodity flow problem, and is solved using ideas from polyhedral combinatorics.

The timetabling algorithm finds a periodic timetable, with a period of 60 minutes. The constraints range from connections to be made to distances to be kept for safety. The problem can be described mathematically as one of finding a potential in a graph satisfying certain conditions. The algorithm uses a decomposition of the problem based on homology classes of solutions. The system we made for NS moreover can optimize the timetable.

We give an introduction to the problems and describe some of the solution methods.

EDGE-COLOURING AND SCHEDULING

We consider the problem of finding and counting perfect matchings in regular bipartite graphs.

The methods have led to the solution of a problem of Erdos and Renyi (1968) on the asymptotic number of perfect matchings in regular graphs, to an improved lower bound on the 3-dimensional Ising constant, and to a fast algorithm for edge-colouring bipartite graphs. This bears upon scheduling school classes.

The algorithm has been speeded up recently by Cole, Schirra, and Ost. We give an introduction to the problems and describe the solution methods.

Inside LEDA
Kurt Mehlhorn

LEDA is a widely used platform for combinatorial and geometric computing. Its distinguishing features are: wide scope, ease of use, correctness, and efficiency. In my lectures, I will give an overview of the library and I will discuss its theoretical and engineering background. In particular, I will discuss the following items:

• correctness and program result verification
• problems in the implementation of geometric algorithms: exact geometry kernels and exact number types.
• issues in algorithm engineering - exploration of design choices - average case analysis - robust worst case and average case instances - analysis of arithmetic demand · an implementation of an O(nm log n) weighted matching algorithm.

The talks will be accompanied by demos.

I will also discuss SCIL (symbolic constraints for integer linear programming).