MPII Home PageMPII Home PageMPII Home Page
ALCOM-FT Home Page
Other Conferences Homepage ADFOCS 2003



Homepage
Program
Excursion




         

MPI Informatik -> Conferences -> ADFOCS 2003 -> Program

Program

We offer four courses. Each course consists of three lecture blocks and two exercise blocks, each block is about 1 1/2 hours long. During the exercise periods, the respective lecturer will be around, as well as some snacks and drinks.

Wednesday, there will be lectures and tutorials in the morning. In the afternoon, there will be an excursion; it's destination will be announced later.



Schedule



September 8
Monday
September 9
Tuesday
September 10
Wednesday
September 11
Thursday
September 12
Friday
8.30-9.00
Registration/Welcome




9.00-10.30 B. Meyer
Lecture
D. Halperin
Lecture
S. Näher
Lecture
R. Bixby / E. Rothberg
Lecture
S. Näher
Lecture
11.00-12.30 D. Halperin
Lecture
B. Meyer
Lecture
R. Bixby / E. Rothberg
Lecture
S. Näher
Exercise
R. Bixby / E. Rothberg
Exercise
12.30-13.30 Lunch Lunch Lunch Lunch Lunch
13.30-15.00 D. Halperin
Exercise
B. Meyer
Exercise

R. Bixby / E. Rothberg
Exercise
S. Näher
Exercise
15.15-16.45 B. Meyer
Lecture
D. Halperin
Lecture
Excursion S. Näher
Lecture

17.00-18.30 B. Meyer
Exercise
D. Halperin
Exercise

R. Bixby / E. Rothberg
Lecture

Evening
Dinner





Lecture(r)s

Below you find short abstracts of the lectures together with an indication of useful prerequisites. Clicking on the photos gets you to the respective lecturers' homepage.

Robert E. Bixby

Rice University / ILOG

The CPLEX Library for
Linear, Mixed-Integer, and
Quadratic Programming

to Robert E. Bixby's homepage

Abstract: We will begin with an introduction to linear programming, including the primal and dual simplex algorithms, and the basics of duality theory and complementarity. Primal-Dual Log barrier algorithms will also be described, though quite briefly. The introduction will contain a summary of computational advances over the last 15 years, including substantial test results and some discussion of application domains for linear and integer programming.

Following this introduction, we will use the simplex ratio test as a vehicle for understanding some of the key issues in a numerically robust implementation of a simplex algorithm. This exposition will lead to an understanding of the notion of perturbation and the closely related notion of "shifting" in dealing with degeneracy in linear programming.

Following the introduction to linear programming, we will provide a very basic introduction to using the CPLEX libraries and Concert Technology to instantiate and solve linear programs.

Ed Rothberg

ILOG

joint course with
Robert E. Bixby

Ed Rothberg (no homepage known)

We will then move on to the topic of mixed integer programming. We will begin with an overview of the basic branch-and-cut algorithm. This will be followed by a discussion of several of the more important components of a modern MIP code. First, we will discuss primal heuristics, which attempt to generate integer-feasible solutions from the solutions to the continuous relaxations solved at each node of the branch-and-cut tree. We will discuss some of the simpler approaches to generating feasible solutions, including various fixing strategies, and we will also discuss more recent approaches that exploit local search notions within a MIP heuristic context to improve known solutions.

We will then discuss MIP presolve and cutting plane techniques. While the two are often viewed as different techniques, both will be be presented within a common framework. The goal in both cases is to modify the continuous relaxation to exclude sets of solutions that can't possibly satisfy the integrality requirements. Particular attention will be paid to knapsack cuts, clique cuts, and Gomory cuts.

Slides: PDF: Bixby_1.pdf, Bixby_2.pdf, Rothberg_1.pdf, Rothberg_2.pdf, Rothberg_3.pdf, Rothberg_4.pdf.
PowerPoint: Bixby_1.ppt.gz, Bixby_2.ppt.gz, Rothberg_1.ppt.gz, Rothberg_2.ppt.gz, Rothberg_3.ppt.gz, Rothberg_4.ppt.gz.

Exercises: Using_CPLEX.pdf, Rothberg_exercises.pdf, Rothberg_examples.tgz.

Dan Halperin

Tel Aviv University

Arrangements and
Their Applications

to Dan Halperin's homepage

Abstract: An arrangement of geometric objects is the decomposition of space induced by these objects. A planar arrangement of a finite set of lines, for example, is the decomposition of the plane into faces, edges and vertices obtained by 'drawing' these lines in the plane. Besides being interesting in their own right, arrangements have emerged over the years as the underlying structure of geometric problems in numerous application domains ranging from optimization through robot motion planning to structural molecular biology.

We start with a brief history of the study of arrangements, reviewing basic concepts, key combinatorial and algorithmic results, and selected applications. We then discuss the difficulties in robust implementation of algorithms for arrangements, together with two approaches to overcoming these difficulties: (i) exact computing and (ii) finite precision approximation. We survey existing software and in particular the CGAL arrangement package. Finally we focus on the application of arrangements to solving motion-planning problems.

Prerequisites: Basic knowledge about algorithms and their implementation. Prior knowledge about computational geometry is not assumed.

Slides: Halperin_1.ps.gz, Halperin_2.ps.gz, Halperin_3.ps.gz.

Exercises: Halperin_exercise_1.ps.gz, Halperin_exercise_2.ps.gz.

Bertrand Meyer

ETH Zürich
Eiffel Software / Monash

Principles of Library Design,
from Reuse and Contracts
to Proofs: the Eiffel Experience

to Betrand Meyer's homepage

Abstract: The future of software engineering will depend in part on our ability to produce reusable components of high quality. The Eiffel experience provides a reference that may be useful to anyone working towards this goal, whether using Eiffel or not. For almost two decades the Eiffel community has been building components for maximum reusability, with a constant emphasis on quality based on a number of original design principles -- Open-Closed, Uniform Access, Single Choice, Single Model, Command-Query Separation, Operand-Option Separation... -- and through systematic application of Design by Contract mechanisms across the component development process.

This set of lectures presents the principles and their consequences, emphasizing generally applicable ideas over language-specific ones. It explores the concept of "trusted components" with guaranteed quality attributes and devotes particular attention to the use of contracts and to the combination of high-level principles with attention to detail. It ends with a presentation of a theory and prospective techniques for producing O-O components with mathematically proved properties.

Slides: PDF: Meyer_1.pdf, Meyer_2.pdf, Meyer_practical_proofs.pdf.
PowerPoint: Meyer_1.ppt.gz, Meyer_2.ppt.gz.

Stefan Näher

University of Trier

Design and Implementation
of Efficient Data Types
for Static Graphs

to Stefan Näher's homepage

Abstract: LEDA contains a very general and powerful graph type. This type provides the operations for all graphs of the library in one single interface. In many situations, however, this general interface is not needed and more specialized implementations of graphs could be used to improve the efficiency of graph algorithms. The lecture presents a new design and an implementation of a family of special and more efficient static graph types which fit into the LEDA environment of graphs and algorithms. They allow to speed up existing programs written with LEDA's standard graph type without changing the underlying code. The efficiency of the new graph data structures will be demonstrated by an experimental evaluation of preflow-push algorithms for the maxflow problem.

Slides: Naeher_1.ps.gz, Naeher_2.pdf, Naeher_2.ppt.gz.

Exercises: Naeher_exercises.ps.gz.

Organization

Concept and web pages borrowed from last year´s
ADFOCS, local organization by Lutz Kettner and Peter Sanders, Petra Mayer, Gabi Holzer and Roxane Wetzel. For comments or questions send an email to adfocs@mpi-sb.mpg.de. Partially supported by the Information Society Technologies Programme of the EU under contract number IST-1999-14186 (project ALCOM-FT ).
ADFOCS 2003 organized by Lutz Kettner and Peter Sanders; WWW page last updated on Wednesday, 17 September 2003.