308-567B   Integer Programming  Winter 2002

Course News                                 Please check at least once a week!

2002.2.22    No class Monday March 4, test Monday March 6.

Material for test:
Integer Programming by Wolsey: chapters 1, 2, 3.1, 3.2, 7.1-7.4 ,
Handouts: Matroids, Branch and Cut for Steiner Problem (section 2)
Homework assignments   (no questions about cplex or lrs!).

Assignment 2 is available at      http://cgm.cs.mcgill.ca/~avis/courses/567/a2.html

lrs programs are available on lab110-*.cs.mcgill.ca machines in /usr/local/pkgs/lrslib-041


Project                                             Managers                                          Consultants

London Police                    Elias Karam                                            Damien Thomas
                                                    Lila Rakesh                                             Guillaume Erbs

Fashion                                   Melanie Beck                                        Andre Guerette
                                                     Charles Fortin                                      Elias Karam
                                                                                                                          Lila Rakesh

Conferences                          Andre Guerette                                  Melanie Beck
                                                      Damien Thomas                              Charles Fortin
                                                      Guillaume Erbs

emails: Melanie Beck <mbeck1@po-box.mcgill.ca>,
                Damien <damien.thomas69@efrei.fr>, thomasd@efrei.fr
                Guillaume Erbs <erbs@efrei.fr>,
                Andre Guerette <aguerette@caramail.com>
                Leila Rasekh <rasekh@management.mcgill.ca>
                Charles Fortin <fortin@math.mcgill.ca>
                Elias Karam <eliaskaram@sympatico.ca>

Course moved to Leacock 31, 11-1230 MW effective Wednesday Jan 23

Cplex "howto" can be found at

Assignment 1 is available at      http://cgm.cs.mcgill.ca/~avis/courses/567/a1.html

 Important dates and mark breakdown    Dates changed 2002.1.21

Wed Jan 30,  Presentation of description of cases, 10 mins per student            (5%)

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

Mon March 4, Class Test                            (30%)

Mon,Wed April 8,10  Final case presentations, 2 cases per class      (20%)

Mon, April 15   Written reports due    (10%)

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.   Wed 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      Mon Feb 18!

Lecture 14: Preprocessing, ch 7.6

Lecture 15: Class test      Mon 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 Mon, Wed April 8 10