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