Program

Robert E. Bixby

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

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

joint course with
Robert E. Bixby

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

Arrangements and
Their Applications

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

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

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

Design and Implementation
of Efficient Data Types
for Static Graphs

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.