and Theoretical Computer Science

Lafayette College

June 20 - June 26, 2004

(Sunday evening through Saturday afternoon)

Cynthia Phillips, Sandia National Laboratories, caphill@sandia.gov

Large instances of hard discrete mathematical problems must be addressed in practice. Often, the most likely avenue to an optimal solution or even a good bounded solution, is integer programming.

We will study:

* the mathematical foundations of integer programming, including - review of linear programming, - IP formulation techniques, - polyhedral theory - separation, - approximation algorithms * some software systems that are used to develop integer programming solutions, such as: - AMPL, - PICO, and - MINTO * some basic applications of integer programming, such as scheduling and sensor placement * experimental algorithmics, and specifically, fair comparisons of integer programming solutions.

**Prerequisites:** Some familiarity with linear programming will be
expected, but coursework is not necessary. Good preparation would be to
read the chapter(s) in an algorithms book such as Cormen, Leiserson,
Rivest and Stein. The group work will include an implementation
component, so some background in programming is desirable. Groups
will be formed to mix participants with primary strengths in mathematics
with those whose primary strengths are in computer science.

Please consult Jon Berry with any specific questions.

Back to Main Page