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.