Lecture Summaries for Computational Intractability         Spring 2011

Prof. David Avis                          Thurs 8:45 - 10:15        

      also check:  announcements      assignments    return to:  course home page
April 14: 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 21: Introduction to NP-completeness. We proved that Directed Hamiltonian Cycle(DHC) and  TSP are NP-hard.
Some general slides on NP-completeness. Reduction for DHC (first 11 slides)   notes

April 28: 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, machine scheduling, partition and subset problems as knapsack problems. We reduced 3SAT to the subset sum problem directly. See slides 35-37 and notes from April 21.
May 5: Golden week holiday.
May 12: 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
May 19: Special guest lecture by Dr. Rudy Raymond  on LP approximation by the multiplicative update method.
May 26: General statement of the simplex method. Cycling example. Introduction to duality. Read  LP2_en.pdf or LP2_jp.pdf and   notes
June 2:   Weak and strong duality theorems and their proofs. notes  (updated June 6)
June 9: 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   
June 16: 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
June 23: The dual simplex method and Gomory's cutting plane algorithm for integer programming. slides      V. Chvatal's notes1  notes2
June 30: 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
July 7: We also discussed branch and bound and branch and cut strategies for integer programming. Bill Cook's slides on solving TSPs are here.  Mathematica notebook.  
July 14: NP-completeness proof for one machine scheduling with release times. Discussion of reports. Course feedback.
July 21: No lecture.