### 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