announce567

COMP 567B Integer Programming Winter 2003

2003.4.3 Revised Dates:

Final Project presentations: Monday April 14, 2-4pm, followed by post mortem at Thomson House.
Tues, April 30 Written reports due.

Links for the recent handouts:

Cplex:

http://www.ilog.com/products/optimization/tech/research/mip.ps

Steiner tree (from Mcgill computers only):

Tuesday March11, Class Test (30%)

Readings for the exam, from Wolsey: Chapter 1, 2, 3.1, 3.2, 7, 8.1-8.6

Assignment 2 due Tuesday March 4 A maple session for Gomory's algorithm

Thursday Feb 20, Proposals for teams working on cases, 20-30 mins per team (5%)

2003.1.21 Here is a nice link to a site with various test data files. Useful for projects!

http://mscmga.ms.ic.ac.uk/info.html

2003.1.23 Assignment 1 (misprint corrected in question 1).

Teaching Assistant: Bohdan Kaluzny (to be confirmed)
McConnell 232 beezer@cs.mcgill.ca http://www.cs.McGill.CA/~beezer

Homework: 3 sets (30%)

Proposed Lecture Schedule

Text book chapters refer to "Integer Programming" by L. Wolsey, Wiley (1998)

Lecture 1-2: Formulations of integer programs, ch. 1.1-1.4

Lecture 3: Polyhedra and ideal formulations, ch. 1.5-1.7

Lecture 4-5: Optimality, relaxation, bounds, ch. 2.1-2.4

Lecture 6: Duality, ch. 2.5-2.6

Lecture 7: Well solved integer programming problems, ch. 3.1,3.3

Lecture 8: "Managers" present introduction to cases. Thurs Jan 30!

Lecture 9: Unimodularity, ch. 3.2 + class notes

Lecture 10: Optimal trees

Lecture 11: Submodularity and Matroids, Ch 3.6

Lecture 12: Branch and Bound, Ch 7.1-5

Lectures: 13: Preliminary presentation of case studies Tues Feb 18!

Lecture 14: Preprocessing, ch 7.6

Lecture 15: Class test Tues March 4

Lecture 16-17: Cutting planes and Chvatal-Gomory procedure, ch. 8.1-8.6

Lecture 18: Mixed integer rounding, ch. 8.7-8.8

Lectures 19-20: Valid inequalities, polyhedral computations ch. 9

Lecture 21-23: Vertex and facet enumeration, class notes

Lectures 24-25: Case study presentations Tues, Thurs April 8 10