Lecture Summaries for COMP
return to: course home page
Jan 6th: Course overview, formulations of integer programming problems: 3-Sat, Partition, travelling salesman and the time dependent travelling salesman.
Read Chapter 1 of Wolsey.
January 11th: Dr. Bohdan Kaluzny, presented an application of Integer
The Optimal MSVS Fleet for First-Line Replenishment and
presented an introduction to aircraft balancing and loading
January 13th: Dr. Bohdan Kaluzny continued with the problem of
Optimal aircraft load balancing (link viewable from McGill computers or VPN)
January 18th: More formulations: assignment problem, 0-1 knapsack problem.
Combinatorial optimization problem (COP) and examples of COPs (partition,
knapsack, TSP). Set covering (facility location) and set packing, duality
of stable set and Covering vertices by edges. Modelling fixed cost
functions and disjunctions.
Jan. 20: Ideal Formulations. An intro to how to use lp_solve, zimpl and cplex
Jan. 25,27: Relaxations and duality. LP, Combinatorial and Langrangian relaxations. Read: Ch.2 of Wolsey
Jan 29: Tutorial. Chapter 1 of Linear Programming, V. Chvatal (on reserve, Schulich Library)Read: Ch 1,2 Linear Programming, V. Chvatal.
Feb 1: Well solved problems. Read sections 3.1, 3.2.
Feb 3: Branch and Bound. Read sections 7.1,7.2,7.3,7.4
Feb 5: Tutorial. Chapter 2,3,4 Linear Programming, V. Chvatal
Feb 8: Dual simplex method, adding a constraint to an optimal LP solution. Introduction to cutting planes. Read: Class handout, Section 10
Feb 10: Gomory's cutting plane algorithm. Read: Class handout, Section 11. slides_pdf slides_ppt
Feb 12 Tutorial: Duality of linear programs. Chapter 5, Linear Programming, V. Chvatal.
Feb 15, 17 Project proposals. See Projects 2010
Notes: Proposals should not be too mathematical. Try to explain the model using as few formulae as possible.
Some helpful references for using "patterns" in integer programming are: cutting stock problem and flight scheduling.
Feb 22, 24 Study Break
Mar. 1: Basic mixed integer inequality. Read: text section 8.7.1
Mar. 3 Mixed integer rounding inequality, Chvatal-Gomory procedure. Gomory mixed integer cut. Read: 8.3, 8.7.2, 8.7.3
Mar. 8 Branch and Cut. Flight Schdeduling problem. Read 9.6 and flight scheduling.
Mar 10 Facets of the knapsack problem. Step by step instructions for this are here. Read: 9.1, 9.2.1,9.2.2, 9.3
Mar 12 Special lecture on travelling salesman problem by Bill Cook. Please attend if at all possible! (Replaces April 7 lecture)
Note time and location: 10:35 AM, Trottier Building 2100
If you missed this talk, take a look at one of these other talks.
Mar 15 Review session
Mar 17 Class test. Based all material above except Jan 11, 13, Feb 15, 17, Mar 12 and mixed integer cuts (section 8.7)
Mar 22 Review of test. Introduction to Cut and Metric polytopes.
Mar 24 More on Cut and Metric polytopes, including hypermetric facets.
Mar 29, 31 Project progress reports. Same schedule a Feb 15,17.
Apr 5. Easter Monday, no class
Apr 7. (Replaced by March 12 lecture on the Travelling Salesman Problem by Bill Cook)
Apr 12, 14 Stochastic optimization with applications to mining. Guest lectures given by Prof. Roussos Dimitrakopoulos.