Lecure on ``Large Scale Optimization'' - SS 2004

Instructors

Lecture: Dr. Ernst Althaus		Building 46 (MPII), Room 304
Tutorial: Kanela Kaligosi		Building 46 (MPII), Room 322

Time and place:

Lecture:	Fr. 14.00-15.30 (we agreed to start 14.00 sharp, without a quarter hour delay), Building 46 (MPII), Room 024
Tutorial:	Fr. 15.45-16.30, Building 46 (MPII), Room 024 (up to discussion)

Topics:

Advanced techniques from combinatorial optimization are typically shown to be effective to solve a single problem. The interplay between different components is evaluated rarley. In this lecture, we describe some every elaborated codes that integrate different state-of-the-art techniques from combinatorial optimization. Those codes wer deliverd over several years, consitst of severtal 10.000th of lines of codes and are now outstanding software packages in combinatorial optimization.

Concorde: A Code for Solving Traveling Salesman Problems. This code received much addention recently. It solves Traveling Salesman Instnaces with up to 17.000 cities to optimally and instances with up to 2 million cities up to 0.1% of optimally.
Algorithms for Steiner Trees. Tobias Polzin (formerly MPI) and Siavash Vadathi Sanshmand developed an algorithm that solves by far the largest Steiner tree problems. It consists of over 60.000 lines of source code.
Lagrangean Relaxation.
Column Generation Techniques.

About the lecture

This is a 6 credit points (6 LP) lecture. There will be 2 hours of lecture per week plus one hour of tutorial session. Basic knowledge on optimization is assumed (it suffices to hear the lecture ``Optimization'' in parralel).

Exercises

Exercise 1. Deadline: May 7th.
Exercise 2. Deadline: May 14th.
Exercise 3. Deadline: May 21th.
Exercise 4. Deadline: May 28th.
Exercise 5. Deadline: June 18th.
Exercise 6. Deadline: June 25th.
Exercise 7. Deadline: July 9th.