###
Course Outline: Discrete
Optimization - 2

###
308-567B
Winter 2002 *Last
Updated: 2002.1.10*

Time: MW 11:00-12:30
Leacock 31

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 solving a variety of integer programs. Each
student will be expected to prepare 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. A written report on the case study is due on the last day 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, avis@cs.mcgill.ca*

*Office Hours: Tu ,Th 11-12pm*

http://www.cs.mcgill.ca/~avis