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 reviewing linear programming, 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: 13:30-14:30 Tu Th
http://cgm.cs.mcgill.ca/~avis
Teaching Assistant: Bundit
Laekhanukit blaekh@cs.mcgill.ca
Office hours: by email appointment
In accord with McGill University’s Charter of Students’ Rights, students in this course have the right to submit in English or in French any written work that is to be graded.
McGill University values academic integrity.
Therefore all students must understand the meaning and
consequences of cheating, plagiarism and other academic
offences under the Code of Student Conduct and Disciplinary
Procedures (see www.mcgill.ca/integrity for
more information).