### Course Outline:
Discrete Optimization - 2

### COMP
567
Winter 2008 *Last
Updated: 2008.1.8*

Time: MW 11:35-12:55
McConnell 103
course home page

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
integer programs by branch and bound, cutting plane and column
generation algorithms. We will also discuss stochastic integer
programming, and additional special topics as time permits.

Students will gain experience by working in teams on a substantial
case study of an application of integer programming.

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).

**Recommended Text: **Integer Programming, by L. Wolsey

**Prerequisites: **COMP566 or
MATH 417/487 or COMP/MATH 551 or a course in linear algebra and
a good knowledge of linear programming.

**Texts on Reserve at PSEAL Library:**

- Integer Programming, by L. Wolsey

- 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: MW 10:30-11*

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

Academic Integrity: Please read http://www.mcgill.ca/integrity/