Lecture Summaries for Computational Intractability
Spring 2012
Prof. David
Avis
Thurs 8:45 - 10:15
Tentative Schedule
also check:
announcements
assignments return to:
course home page
April 12: We discussed formulations of the
knapsack problem and the travelling salesman problem as integer
programs. notes
See announcements to get information on lp_solve. The TSP homepage
is at http://www.tsp.gatech.edu/
April 19: Using lp_solve for
the TSP problem. Sample lp_solve files are here.
Introduction to NP-completeness.
Some general slides on
NP-completeness (we did first 18). notes
Exercise: Solve the TSP
on 5 cities using lp_solve with edge weights:
w12=w13=w21=w25=w31=w34=w42=w53=2 and all other weights equal to
one.
At first do not use any subtour constraints, and use a linear
programming relaxation. Add subtour constraints one by one until you
reach an optimum solution. If you get a fractional LP solution then
add the "binary" condition and solve as an integer program.
April 26: We proved that
Directed Hamiltonian Cycle(DHC) and TSP are NP-hard. We
considered linear programs with only one constraint, and the
corresponding integer program with binary variables, called the
Knapsack problem. Formulation of the sushi problem, partition and
subset problems as knapsack problems. We reduced 3SAT to the subset
sum problem directly. Reduction for DHC (first 11 slides) See slides 35-37 and notes from April 19.
Exercise: Create two
3SAT inputs with about 5 variables and at least 10 clauses. One
input should be satisfiable, and the other one should not be
satisfiable. Now construct the subset sum problems corresponding to
these inputs. Convert the subset sum problems to knapsack problems
and solve them both using lp-solve. Solve using binary
variables and also by using the LP relaxation where each variable is
between zero and one.
Note:
The numbers may turn out too big to solve correctly using 32 bit
arithmetic. In this case you need to decompose them into smaller
integers.
Eg. a 16 digit integer can be considered as two 8 bit integers. Each
of the 8 bit parts needs to add up to the correct number.
In this case you need an integer program with more than one
constraint, so it is not strictly speaking a knapsack problem. (This part of the problem for extra
credit)
May 3: Golden week holiday.
May 10: Inroduction to LP. This may be the most
important lecture of the course, as everything will build
on this. Therefore is essential to understand the reading material LP_en.pdf or LP_jp.pdf and notes
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.
May 17: General statement of
the simplex method. Getting a feasible starting solution. Cycling
example. Read LP2_en.pdf
or LP2_jp.pdf and notes
Exercise: (corrected
May 31) (a) Prove that if variable x_j leaves the basis during
iteration k of the simplex method, it cannot enter the basis on
iteration k+1.
(b) Show by finding a specific example that it could however enter on iteration k+2.
(c) Nevertheless, use (a) to prove that the smallest length cycle
possible for the simplex involves at least four pivots.
(d) (Optional for extra credit) Show by an example LP with at least
two constraints that a variable can enter the basis at iteration k and leave it at iteration
k+1
May 24: Duality.
Weak and strong duality theorems and their proofs. Read notes
Exercise: Do the
exercise at the end of the notes
May 31: We looked at the
Uncapacitated lot size (ULS) problem with and without fixed costs.
We saw two formulations for the case with fixed costs. The second
one has only integer vertices, so linear programming will give an
optimum integer solution. Some notes on the vertex enumeration part
using lrs are here. See announcements
page for instructions on installing lp_solve and lrs. notes input
files
Exercise: Consider an
instance ULS with n = 5, demands d = (5, 4, 2, 3, 6), variable
production costs p = (3, 1, 3, 2, 1), and fixed production costs f =
(20, 30, 25, 15, 5). Formulate the problem as an ILP using both
formulations in the notes. Solve each formulations using lp_solve
both as (i) an ordinary LP and as (ii) an ILP
Bonus: Consider the
problem where the fixed cost only has to be paid if the production in the previous
period was zero.
(This is now a start-up cost). Give an integer programming
formulation for this and solve the previous problem again using this
new objective function.
June 7: Crew scheduling
problem. We formulated it as a linear program, and studied the
structure of the underlying polyhedron.
The files we used in class for lp_solve and lrs are here. notes
Exercise: In our
current formulation, a crew can end the day in a different city than
they started from. The company wants to change the policy so that each crew ends up in the same
city that they started from. So in the example, the pairing
1235 is not valid as the crew starts in DFW and ends in LGA. In such
a paring the company must add an extra flight (with only the
crew) from LGA to DFW leaving at 21h. Note this extra flight
only needs to covered if the pairing 1235 is used.
Show how to model this new version of the problem. Illustrate on the
example in the notes using LP-solve and the 3 objective functions
given in Section 3 of the notes.
(The objective function in equation (3) has to be modified to
include the cost of any extra flights)
June 14: The dual simplex
method and Gomory's cutting plane algorithm for integer programming.
slides V.
Chvatal's notes1 notes2
The big picture is here!
(thanks to Atsuki)
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.)
June 21: Special guest
lecture by Bill
Cook: Exact
computations for LP and MIP, including Gomory cuts.
His acclaimed book on the travelling salesman problem is available
on amazon
and if you bring a copy to class, he will likely sign it for you!
No exercise.
June 28: We studied two
completely different integer programming formulations of the one
machine scheduling problem with precedence constraints and release
times. The objective was to minimize weighted completion time. See
the wiki. notes
Exercise: Prove the
correctness of Smith's rule for minimum weighted completion time
with no precedence relations (notes, Section 1.2)
Bonus: Let y_ij = 1 if
job i is the j-th job to be processed, for i,j=1,2,...,n (and =0
otherwise).
Eg. Jobs scheduled in order 3 1 4 2 would have y_31=1, y_12=1,
y_43=1, y_24=1 and all other y_ij=0.
Show how to write these variables in terms of the variables x_ij
defined in the notes Section 1.4.
You may only use linear
equations and/or inequalities to do this.
You need to show that any feasible assignment of 0/1 to the x
variables (ie. a permutation of the jobs) gives the correct
corresponding assignment of the y variables and vice
versa.
(Thanks to Long Cheng for this idea)
July 5: We also discussed branch and
bound and branch and cut
strategies for integer programming. Vardges Melkonian's slides
bb1.ppt, bb2.ppt
The big picture is here!
(thanks to Atsuki)
Exercises: (1) In slides
directory open the file bbextra.ppt and answer all questions.
(2) Solve the problem given on slide 3 of the Gomory algorithm
slides using branch and
bound. Draw the branch and bound tree giving the LP solution at each
node of the tree, and explaining why each leaf is fathomed.
July 12: Third report due! NP-completeness proof
for one machine scheduling with release times. Discussion of
reports. Course feedback.