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

Exercise:

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

Exercise:

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

Exercises:

(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, c

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)

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

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.