


Homepage
Program Excursion 


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.
September 8 Monday 
September 9 Tuesday 
September 10 Wednesday 
September 11 Thursday 
September 12 Friday 


8.309.00 
Registration/Welcome 

9.0010.30  B. Meyer Lecture 
D. Halperin Lecture 
S. Näher Lecture 
R. Bixby / E. Rothberg Lecture 
S. Näher Lecture 
11.0012.30  D. Halperin Lecture 
B. Meyer Lecture 
R. Bixby / E. Rothberg Lecture 
S. Näher Exercise 
R. Bixby / E. Rothberg Exercise 
12.3013.30  
13.3015.00  D. Halperin Exercise 
B. Meyer Exercise 
R. Bixby / E. Rothberg Exercise 
S. Näher Exercise 

15.1516.45  B. Meyer Lecture 
D. Halperin Lecture 
Excursion  S. Näher Lecture 

17.0018.30  B. Meyer Exercise 
D. Halperin Exercise 
R. Bixby / E. Rothberg Lecture 

Evening  Dinner 
Robert E. BixbyRice University / ILOGThe CPLEX Library for 
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. PrimalDual 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 RothbergILOGjoint course with 
We will then move on to the topic of mixed integer programming. We will begin with an overview of the basic branchandcut 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 integerfeasible solutions from the solutions to the continuous relaxations solved at each node of the branchandcut 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. Exercises: Using_CPLEX.pdf, Rothberg_exercises.pdf, Rothberg_examples.tgz. 

Dan HalperinTel Aviv University Arrangements and 
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 motionplanning 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 MeyerETH ZürichEiffel Software / Monash Principles of Library Design, 
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  OpenClosed, Uniform Access, Single Choice, Single Model, CommandQuery Separation, OperandOption 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 languagespecific 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 highlevel principles with attention to detail. It ends with a presentation of a theory and prospective techniques for producing OO components with mathematically proved properties. Slides: PDF:
Meyer_1.pdf,
Meyer_2.pdf,
Meyer_practical_proofs.pdf. 

Stefan NäherUniversity of TrierDesign and Implementation 
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 preflowpush algorithms for the maxflow problem. Slides: Naeher_1.ps.gz, Naeher_2.pdf, Naeher_2.ppt.gz. Exercises: Naeher_exercises.ps.gz. 
