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
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, 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. noteslp_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
notes1notes2 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 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:
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.