COMP 567B Discrete Optimization - II
Winter 2004
Course News
Please check at least once a week!
2004.4.7 Machines in the lab9-j.cs.mcgill.ca series have been reserved for
our course.
The
door is locked, so noone should be able to reboot the machine while
your cplex job is running.
Please use these machines!
2004.3.31 No class on April 6 and 8, presentations on Wed April
14 from 3pm.
A
CPLEX document that is quite interesting is here.
2004.3.24 Assignment 3, due April 13.
2004.3.16 I put a couple of old class tests here.
Note the material varies from year to year: eg. in 2002 we covered matroids.
I'll be in my office wednesday 3-5pm if you have questions.
2004.3.12 Midterm onThurs March 18 covers all readings up to March 16.
Wolsey: Chapters 1,2,7.1-7.4, 8.1-8.6 (except proof of theorem 8.4),
SDP notes from Miguel's lectures
Sections 1-3, and 5.
2004.3.1 Full set of notes
for Miguel Anjos's lectures on SDP.
2004.2.11 Assignment
2, due February 19.
Some information on case studies.
2004.2.9 CPLEX should now be up and running on many
machines. Notes on course software are here
2004.1.21 Assignment 1,
due January 29.
.
2004.1.20 Here is some information on some alternate
texts:
Integer Programming and Combinatorial Optimization ,
W. Cook et al. 2002.
A recent book with lots of very nice proofs and material
supplemental to what we will be studying.
Combinatorial Optimization, Papadimitriou and Steiglitz, 1982
Despite its age, one of the best all round books on
LP, ILP, Combinatorial Optimization and Complexity.
Integer and Combinatorial Optimization, Nemhauser and Wolsey,
1988, revised 1999
The revised version (paperback) is similar to
the original, which is a good solid theoretical study
of IP and CO. Lots of examples and exercises.
Combinatorial Optimization, A. Schijver, 2003
Box set, 3 volumes, 1800 pages all for $140. A tour
de force, but covers mostly the polynomial time side of the subject
which we are not emphasizing in 567.
Theory of Linear and Integer Programming, A. Schrijver, 1986
Very dense and comprehensive, best as a reference book.
I have all these in my office if you would like to take a
look.
Teaching Assistant: Bohdan Kaluzny
Office Hours: MW 1030-1130,
McConnell 232
beezer@cs.mcgill.ca
http://www.cs.McGill.CA/~beezer
Homework: 3 sets
(30%)
Proposed Lecture Schedule (Dates
revised 2004.2.18)
Text book chapters refer to "Integer Programming"
by L. Wolsey, Wiley (1998)
Lecture 1: Formulations of integer programs, ch.
1.1-1.4
Lecture 2: Polyhedra and ideal formulations, ch.
1.5-1.7
Lecture 3: Optimality, relaxation, bounds, ch.
2.1-2.4
Lecture 4: Duality, ch. 2.5-2.6
Lecture 5-6: "Managers" present introduction to cases. Tues Jan 27-Thurs Jan 29
Lecture 7: Combinatorial Duality. Lagrangian Relaxation.
Lecture 8: Max cut and linear programmming relaxations.
(handout)
Lecture 9-12: Semidefinite Programming and Max Cut
Lectures given by Miguel Anjos. Lecture
Notes.
Lectures: 13-14: Consultants present proposals for
case studies. Tues March 2 - Thurs March 4
Lecture 15: Branch and Bound and Preprocessing, ch
7
Lecture 16-17: Cutting planes and Chvatal-Gomory
procedure, ch. 8.1-8.6
Lecture 18: Class test
Thurs March 18
Lectures 19-20: Valid inequalities, polyhedral computations
ch. 9
Lecture 21-22: Vertex and facet enumeration, class
notes
Lectures 23-24: Case study presentations Tues, Thurs April 6, 8