Lecture Summaries  for COMP 567                    Winter 2010

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 
Programming:

http://cradpdf.drdc.gc.ca/PDFS/unc88/p527153.pdf
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 
http://www3.interscience.wiley.com/cgi-bin/fulltext/122660693/PDFSTART
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.