Lecture Summaries  for COMP 567                    Winter 2007

      also check:   news                        return to: course home page

Jan. 3: No class

Jan 8: Discussion of class projects and some sample projects and ideas.

Jan 10: Introduction to integer programming via comparison of assignment problem and travelling salesman problem (TSP).
LP relaxations, subtour constraints and comb inequality.

Jan 15: Guest lecture by Vasek Chvatal on the Assignment problem.

Jan 17: Students present project suggestions (5-10 mins each)

Jan 22: Formulations. Read Ch 1 of Wolsey.

Jan 24: More on formulation. Two formulation of Uncapacitated Lot Sizing.

Jan 29: Relaxations: LP, Combintorial and Langrangian. Read Ch 2 of Wolsey.

Jan 31: Vasek's second guest lecture.

Feb 5: Duality. Valid Inequalities. Text: 8.1-8.3.1

Feb 7: Cutting Planes for integer programs. Text 8.3.2, 8.5

Feb 12: Cutting Planes for mixed integer programs. Text 8.7  Assignment 2.

Feb 14: Consultant teams give proposals.

Feb 19, 21: Study Break.

Feb 26: More on mixed integer cutting planes. The Gomory mixed integer cut.
Disjunctive inequalities. Text 8.7.3, 8.8

Feb 28: Strong valid inequalities. Cover inequalities for the Knapsack problem. Text: 9.2.2, 9.3

Mar 5: Xu Huan's lectures on Stochastic Optimization. Text on reserve in Schulich library:
Introduction to stochastic programming / John R. Birge, Francois Louveaux
The farmer problem. Read: Start reading Chapter 1.

Mar 7: News vendor problem. Finish reading Chapter 1.

March 28 class test covers all material up to Mar. 7 (except Jan 8, 15, 17, 31, Feb 14) plus the three assignments.

Mar 12: Recourse problem. Risk aversion. Stochastic facility location.

Mar 14: Algorithm for two stage linear recourse problem.

Mar 19: Example of two stage linear recourse problem. Formulation of simple recourse problem as equivalent LP.

Mar 21: Stochastic integer programming.

Mar 26: Election day, no class.

Mar 28  Class Test

April 2, 4 Preliminary findigns and progress report.

                 return to: course home page