DIMACS
The Center for Discrete Mathematics
and Theoretical Computer Science

Reconnect Satellite Conference 2004:
Lafayette College

Reconnecting Teaching Faculty to the Mathematical Sciences Enterprise

June 20 - June 26, 2004
(Sunday evening through Saturday afternoon)


Experimental Algorithmics, with a Focus on Branch and Bound for Discrete Optimization Problems
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