Lecture Summaries  for COMP 567                    Winter 2008

      also check:   news                        return to: course home page

Jan 7 and 9: Course overview, formulations of integer programming problems:  assignment, travelling salesman, minimum spanning tree, facilities location(set cover), project selection(set packing). Read Chapter 1 of Wolsey.

Jan 14: More about formulations:  fixed costs, disjunctions, ideal formulations. Read: From Ch. 1, Wolsey.

Jan 16: Initial presentations of problems for consideration as course projects. See casestudy.html

Jan 21: Remaining project presentations. Alternate formulations. Uncapacitated lot sizing. Notes given in class and lrs input files are here.
Jan 23: Optimality and relaxations. Read: Ch 2 of Wolsey

Jan 28: Branch and Bound. Read: Ch 7 of Wolsey

Jan 30: Valid inequalities. How to generate valid inequalities for LPs. Using lrs. Read: pp113-117

Feb 4: Strong valid inequalities for integer programming. Chvatal-Gomory procedure. Chvatal rank of an inequality. Read: 117-120 (not responsible for proof of Thm 8.4

Feb 6: Gomory's cutting plane algorithm. Cover inequalities for the knapsack problem. Read: sections 8.5, 8.6, 9.3.1 slides_pdf  slides_ppt
Feb 11: Review session.

Feb 13: Class Test. (Covers: All material above up to and including Feb 4, and both homework assignments.)

Feb 18: Mixed integer cuts. Read: Wolsey section 8.7

Feb 20:  Proposals by consultants. See casestudy.html
Feb 25, 27: Study Break

Mar 3: 0-1 Knapsack inequalities. Read Wolsey section 9.4. Other material taken from ez, knt. Recent interesting results are in egp.

Mar 5: Conor on Cplex.

Mar 10: The Steiner Tree problem. We looked at the paper  "A branch and cut algorithm for the Steiner problem in graphs", A. Lucena & J. Beasley, Networks (31) 39-59, 1998.

Mar 12: The Travelling Salesman problem.   Bill Cook's talk.  Also check out the subtour applet.

Mar 17: Xu Huan's lectures on Stochastic Optimization. Attendance compulsory!
Text on reserve in Schulich library: Introduction to stochastic programming / John R. Birge, Francois Louveaux.
The farmer problem. Read: notes1

Mar 19: Stochastic Optimization 2. News vendor problem. Read: notes2
Thurs Mar 20: No lecture.  (University make up day for Mar. 24).   Informal discussions between management/consultant teams - please arrange by email.

Mar 24: Easter Monday holiday.

Mar 26: Stochastic Optimization 3. Algorithm for two stage linear recourse problem. Read: notes3
   Assignment 3 posted

March 31 and April 2: Guest Lecturer, Yosuke Kikuchi, on the Stable Marriage Problem. Read: slides1   slides2

April 7: 12 noon start. Progress report.   A to Z Logistics Co.
Consultants Ali and Behnaz.

April 10: Preventative Healthcare Facilities
Consultants  Julia and Paul.

Mine Planning: Long Term Production Scheduling
Consultants Francisco and Yang

4:30pm: Feedback session at Thomson House, 3650 McTavish  (Non-members will be signed in.)