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.)