Course Outline:         Discrete Optimization - 2

 308-567B                   Winter 2004       Last Updated: 2003.12.4

 Time: Tu-Th 4:05 -5:25         McConnell 103

This course is concerned with the formulation and solution of integer programs, and their application to a wide range of problems in operations research and combinatorial optimization. Integer programs are used to model situations where some of the variables are indivisible, for example 0/1 variables which model decisions. Typical applications include scheduling problems, vehicle routing, telecommunication networks, electricity generation and cutting stock problems. Although these problems are difficult to solve in general, many important classes admit efficient algorithms. In addition, even fairly large NP-hard integer programs may now be solved in a reasonable ammount of time by modern methods. In this course we begin by studying formulations and general solutions methods by relaxation. We will see how to recognize and solve efficiently important classes of integer programs, including network flows, matchings and certain matroid problems.

The second part of the course is concerned with solution of NP-hard integer programs by branch and bound, cutting plane and column generation algorithms. We will also discuss Langrangian duality and some heuristic solutions including tabu search, simulated annealing and genetic algorithms.

Students will gain experience by working in teams on a substantial case study of an application of integer programming. This study will involve the solution of a realistically sized integer programming problem on a reasonably large set or sets of data.
Initially each student will provide a short description in class of a possible case study. This may be invented, or modified from some existing study. State what input data will be available, and what problem is supposed to be solved. Each student will then become a member of two teams: a management team and a consultants team (2-3 students per team). Each consultants teams will attempt to solve one of the cases presented earlier. The managers will provide a more complete description of the project, and in particular provide all necessary test data. The consultants will present a complete proposal in class (about mid-term) and a complete presentation of their solution at the end of term.

There will be an in-class test following the first two parts of the course, worth 30%. The case study will count 40%, and the remaining 30% of the mark will be from homework. Some of the homework will involve computation with a commercial integer programming package (eg. CPLEX).

Required Text: Integer Programming, by L. Wolsey
Prerequisites: 308-566A or good knowledge of linear programming.

Texts on Reserve at PSEAL Library:
- Integer and Combinatorial Optimization, by Nemhauser and Wolsey
- Theory of Linear and Integer Programming, by Schrijver
- Combinatorial Optimization, by Cook, Cunningham, Pulleyblank, Schrijver

Professor David Avis
McConnell 308, Phone: 398-3737,
Office Hours: Tu ,Th  11:30-12:30pm

Teaching Assistant: Bohdan Kaluzny
McConnell 232 http://www.cs.McGill.CA/~beezer
Office Hours:   MC232,    MW 1030-1130

Academic Integrity: Please read