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