Lecture Summaries for Computational Intractability         Spring 2010

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

      also check:  announcements      assignments    return to:  course home page
The first part of the course will cover Chapters 7,8 and 9 of Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani.
April 8: 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/
Please try these exercises.

April 15: Introduction to NP-completeness. We proved that TSP and knapsack are NP-hard, by showing that Hamilton circuit and Subset Sum are NP-complete.
The slides we used are in the hidden folder. Please contact me or Hiroki Morizumi for its location. notes

April 22: Introduction 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 in the hidden folder. Exercise: 2.1 (a),(b) and (c) from the readings.   notes

April 29: No lecture. Why not solve an LP?

May 6: More on the simplex method: termination and initialization.
Read LP2_en.pdf  or LP_jp.pdf in the hidden directory. Also try out yourself the two phase method when the origin is not feasible.  notes

May 13: Introduction to duality theory. Weak and strong duality theorems. notes

May 20: 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 and here. See announcements page for instructions on installing lp_solve and lrs. notes
Exercises:
1. Get a copy of lp_solve and lrs on your computer. Construct the lp_solve and lrs input files for the first formulation of ULS when n=4 for some reasonable values of the input data.
Find input data where the lp_solve LP solution is integer valued, and data for which the LP solution is fractional. Also compute all the vertices using lrs for each case.
Can you give a characterization of the vertices for the first formulation of ULS?

2. Assume that all costs are positive. Find a necessary and sufficient condition on the input data for the first formulation to give an integer solution, when solved as a linear program.
May 27: 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 3: The dual simplex method and Gomory's cutting plane algorithm for integer programming. slides
June 10: No class, please work on project.
June 17: We studied two completely different integer programming formulations of the one machine scheduling problem with precedence constraints. The objective was to minimize weighted completion time. Notes to follow. There are many variations of today's scheduling problem which are suitable for projects. See the wiki.   notes
June 24: We discussed branch and bound and branch and cut strategies for integer programming. 
July 1: We returned to the one machine scheduling problem and considered two additional formulations. Then we looked at some computational results. Read this paper.
July 8: Facets of the Knapsack polytope. We studied cover inequalities, extended cover inequalities and lifting. Read pp 67-72 of this book. lrs files and explanation.
July 15: (Last Lecture) Travelling Salesman Problem.