Lecture Summaries  for COMP 567                    Winter 2012

      also check:   news                        return to: course home page

Please report any errors in the lecture notes, thanks!

Jan 9: First lecture. Course outline. Basic notions of the class NP, NP-hard and NP-complete. Read Text Chapter 6 and the first four pages of notes

Jan 11: We discussed formulations of the knapsack problem, assignment problem and the travelling salesman problem as integer programs.Read Wolsey Ch. 1 and notes

Exercise: Consider solving the knapsack problem (1) in notes as a linear program, ie. forget about the integer condition and just suppose 0 <= x_j <= 1 for j=1,...n.
(a) Explain how to solve this efficiently. (Hint consider the ratios c_j / a_j ).
(b) Show by example that this does not solve the problem for 0/1 variables in general.
(c) For which types of knapsack problems is the LP solution also the optimum the integer solution?

Jan 16: Linear programming and the simplex method. Read: Ch 1 and Ch 2 of Linear Programming, V. Chvatal (On reserve in Shulich Library) and notes
This lecture is fundamental to the course. DO THIS EXERCISE!!

Exercise: Write down your own LP with two constraints and four variables (or more!) and solve it by hand according to the method in today's lecture.

Jan 18: Geometry of the simplex method. Getting a feasible solution by the 2-phase method. Comments on pivot rules and cycling.Read Ch 3 of Linear Programming. notes

(1) For your exercise for Jan 16 make one or both of b_1 , b_2 negative. Now find a feasible solution, if one exists, by doing Phase 1 of the simplex method.

(2) Do the exercise at the end of the notes         (Ie.  "Apply this rule to Fukuda’s example and see that it does not cycle"? )
Assignment 1: Exercises for the lectures on Jan 9,11,16,18 due on January 25 in class.   Assignment 1 (pdf)

Jan 23: Combinatorial optimization problems: abstract view of problem formulation. Discussion of course project part 1: initial description of projects. See 2010 descriptions and case study.
Formulate the project assignment problem as an integer LP.
(a) 3n students. Student s_j prepares a description of  project p_j, j=1,2,...,3n
(b) Each student ranks only those projects they are interested in working on and assigns a score of 1 to 10 to each (10 is best score). No student can work on their own project.
Eg. Student 4 wants to work on projects 5, 8, 11, 12 with scores 4,10,10,6 respectively.
(c) Your job is to divide the students into n teams of 3, each team getting a different project, to maximimze the total score.
(d) Note the problem as stated may not have a feasible solution. Discuss how to modify the above procedure to always allow a feasible solution.

Jan 25: Cplex and the solution of the N queens problem. Input file is here. Animation of backtracking is here. Modelling fixed costs and the uncapacitated lot size problem (ULS). Text sections 1.5 and 1.6.
Exercise: (P.21, #13) Formulate the following ULS problem using both formulations. Use Cplex to solve both formulations. Also try solving both formulations as linear programs by replacing the binary constraints on y_j by 0 <= y_j <= 1.
Data: n=6, demands=(6,7,4,6,3,8), unit costs=(3,4,3,4,4,5), fixed costs=(12,15,30,23,19,45), storage costs=(1,1,1,1,1,1), maximum production per period=10.

Jan 30. Duality of linear programs. notes
(a) Construct your own example an LP with at least 2 variables and two constraints for which both the primal and dual are infeasible.
(b) You are given an LP:  max cx, Ax <= b, x>=0 such that:
      A has no rows which are all zero, c is not the zero vector,  cj >= 0 for j=1,...,n and aij <= 0 for i=1,...,m and j=1,...,n.
      Use the weak duality theorem to show that this LP is always unbounded.

Feb 1: Optimality, relaxation, bounds. Read Ch. 2.
Exercise: P. 34, Ex. 4       Case study description due today!

Feb 6: Crew scheduling problem. notes     lp_solve data_files

Exercise: Using the example in the notes, the airline wishes to consider the effect of delaying Flight 8. There are two scenarios:
(a) Flight 8 has times 19-21 
(b) Flight 8 has times 21-23.
For each scenario give the flight connection graphs and pairings table.
Then solve the new problems using Cplex or lp_solve with each of the two objective functions:
(i) minimize number of pairings
(ii) cost of a pairing is the time interval between first departure and last arrival + 5 ,ie. like equation (3).

Feb 8: Well solved problems. A sufficient condition for total unimodularity. Minimum cost flows.
Read: Text Ch. 3.1,3.2,3.3  Extract from Papadimitriou & Steiglitz
No exercise.

Assignment 2: Exercises for the lectures on Jan 23,25,30, Feb 1,6,8 due on March 5 in class.(Note new date!) Assignment 2 (pdf)
Feb 13: Proposals by the three groups with 3 consultants per group.

Feb 15: Proposals by the two groups with 4 consultants per group.
Feb 20, 22 Study break.     Please be sure to send your proposal pdf file to Gary

Feb 27: Guest lecture by Bohdan Kaluzny on scheduling security at the Vancouver winter olympics
Feb 29: The dual simplex method and Gomory's cutting plane algorithm for integer programming. slides      V. Chvatal's notes1  notes2
             Must read: Rediscovery of Gomory cuts in the 1990s pdf
Exercise: Solve the following LP by Gomory's method sketching each LP opt solution, as in the slides.
                max x_2 s.t  -3x_1 + 2x_2 <=0, 3x_1 + 2 x_2 <=9, x_1,x_2 >=0 and integer.
(You may use software such as maple, mathlab, excel etc. to solve the system of equations after each pivot step.)

Mar 5: Branch and bound and branch and cut. Read: Sections 7.1-7.4, and 9.6.
Mar 7: Valid inequalities for LPs, ILPs and the Chvatal-Gomory procedure. Read: Sections 8.1-8.3 (except the proof of Thm 8.4)
            A very good description of C-G procedure is in Jochen Konemann's slides (48-71)

Mar 12: Cover inequalities for the Knapsack problem. Read: 9.1, 9.2.1, 9.3.1, 9.3.2
Exercise: P. 162 No. 3

Mar 16: (Makeup lecture for April 11) Please try to attend if you can. Miguel Anjos (Polytechnique) "(Semi)Definitely Going Global!"
              McConnell 103, 3:30pm  (beer afterward!)    

Mar 19: Class test (ARTS 145) All material in reading assignments above up to and including Mar 12 and the first two assignments.
                                                  Feb 13-27 inclusive is not covered on the test.

Mar 19: (Makeup lecture for April 16) Please try to attend if you can.  Bill Cook, In pursuit of the travelling salesman, Concordia,
             Henry Hall Building, 1455 de Maisonneuve West, H-763, 6-8pm.
Mar 21: Single machine scheduling. Read notes.

Exercise: Prove that Smith's rule gives the optimum solution for weighted completion time with no precedence or release times.
Mar 26: Second solution to single machine scheduling problem. Read notes for Mar 21.
Exercise: Suppose in addition to precedence and release times, we are also given a deadline d_j for each job j.
The lateness of a job is given by l_j =max(0, c_j - d_j). Show how to formulate the problem of minimizing the maximum lateness of any job, in both models discussed in the

Mar 28: The vertex enumeration problem. Solution by dictionaries and graph search  notes .    Please also review these slides.
Exercise: Use the brute force method of Section 2 of the notes to classify all cobases of the following system:
1+x1 ≥ 0,  1-x1+x2-x3 ≥ 0,  1 -x1-x2-x3 ≥ 0,  1+x1+x3 ≥ 0,  1+2x1+x2-x3 ≥ 0,  1+2x1-x2-x3≥0
Your solution should include (1) a complete classification of all 20 subsets chosen in step 1 (2) a graph like Figure 7 (3) a sketch like Figure 2

Mar 30: (Another makeup lecture, please try to attend if you can) MC103, 15:30 - 16:30:
"A Stochastic Programming Based Approach to Assemble-to-Order Inventory Systems"     by Marty Reiman, Bell Labs

Apr 2: Progress reports.  Group 1, Group 2     Projects page

Apr 4:     Progress reports. Group 3, Group 4, Group 5

Apr 9:  Easter Monday holiday, no class.
Apr 11: See March 16.

Apr 16: See March 19. No lecture but optional Assignment 3 due at 10am. Exercises from Feb 29, Mar 12,21,26,28.