Lecture Summaries for Computational Intractability         Spring 2013

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

      also check:  announcements      assignments    return to:  course home page
April 11: We discussed the notions of P and NP and integer programming formulation of the knapsack problem. notes
See announcements to get information on lp_solve.
Exercise: Visit a kaiten sushi shop (or make up some reasonable data). Select 15 or more plates and for each plate i record the price p_i and a score r_i. The score is an integer in the range 0..100 that tells how much you like that piece of sushi (100 is best). Note you can give different scores for the same kind of fish: eg. you may see 4 plates of toro and give scores 78,84,85,92 respectively.
Your problem is to decide the best selection of plates to choose given budgets of 1,000, 1,500 and 2,000 yen. Solve each problem using lp_solve. Probably you do not really like the optimal solutions (e.g too much or too little of some kind of fish). Add additional constraints to get a more appetizing solution, and rerun using lp_solve.

April 18: Introduction to NP-completeness.
Some general slides and  notes .
Exercise: Show the following problems are NP-complete. You may assume that both 3-SAT and SUBSET-SUM are NP-complete (see notes for definitions)
1. 3-PARTITION   Input: n integers  Output is "yes" if they can be partitioned into three sets of equal weight.
2. 3-MACHINE SCHEDULING Input: n integers that are running times and a deadline t. Output is "yes" if all jobs can be completed by time t using 3 machines.
3. 4-SAT    Same as 3-SAT but each clause contains exactly 4 literals.
April  25: Formulation of matching and TSP problems. We proved that Directed Hamiltonian Cycle(DHC) and  TSP are NP-hard. We reduced 3SAT to the subset sum problem directly. Reduction for DHC (first 11 slides) See slides 35-37 and notes from April 18.
Exercise: 2-TSP. Here we have 2 salesman and the job is to find two disjoint routes that cover all the cities and have minimum total weight. Eg. if n=7 then the tours could be 1 3 4 6 1 and 2 5 7 2. To get the total weight just add up the weights of the two tours.
Input: integer n and positive integer weights w_ij, 1 <= i,j <= n. Output: Two tours that have minimum total weight and visit each city exactly once. For the decision version, given also integer k and we ask "are there two disjoint tours with total weight at most k"
1. Prove the decision version of 2-TSP is NP-complete (hint: reduce TSP to 2-TSP)
2. Write down an integer programming formulation for the optimization version of  2-TSP 
First report due May 9 in class and consists of exercises for April 11,18,25.
May 2: Monday schedule, no class.
May 9: 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: Start with the LP in the notes and consider changing the objective function so that:
(a) There are exactly two distinct optimum dictionaries
(b) There are exactly three distinct optimum dictionaries
(c) There are exactly four distinct optimum dictionaries.
In each case the initial dictionary (B={4,5}) should not be an optimum dictionary.
In each case pivot from the initial dictionary to an optimum dictionary and argue why the number of optimal dictionaries are as given.
(Hint: consider the geometry !)
May 16: General statement of the simplex method. Getting a feasible starting solution. Cycling example.  Read  LP2_en.pdf or LP2_jp.pdf and   notes
Exercise: From   LP2_en.pdf do exercise 3.9 on p. 44, all three parts.
May 23:   Duality. Weak and strong duality theorems and their proofs. Read  notes 
Exercise: Write down the dual of each problem in ex 3.9 (May 16).
In each case figure out exactly the situation of the dual problem (optimum solution or unbounded or infeasible) and compare with primal outcome.
You results should be consistent with the table on page 5-6 of the   notes 
May 30: 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   
A proof that the formulation in Section 4 gives integer solutions was obtained by Wolsey.
Exercise: Consider an instance ULS with n = 5, demands d = (5, 4, 9, 3, 6), variable production costs p = (3, 1, 3, 2, 4), and fixed production costs f = (20, 30, 25, 10, 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
June 6: 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: (a) Given as input a list of n flights which define a flight graph, find an O(n) time algorithm to construct the flight connection graph.
(b) Construct sets of flights that result in an exponential number of pairings. (Ie. number of pairings grows as c^n for some positive constant c)
Second report due June 13 in class and consists of exercises from May 9 to June 6
June 13: 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: Using the cutting plane method shown on the slides to show there is no integer solution to max x1+x2 st. x1 >= 1/2,  x2 >= 1/2, x1+x2 <= 3/2.
Show the optimum (or infeasible) dictionary at each step and how to derive the cutting plane. (You do not need to show all the details of the pivots).
June 19: Extra lecture (no exercise) Bill Cook goes in search of the travelling salesman. Research Building No. 8, Room 328
                          (Building 59 on this map )
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!
June 20:  Special guest lecture by David Bremner: Finding a minimum norm point on a polyhedral boundary

June 27: 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: Use the precedence graph in the notes and generate a set of process times and weights for the seven jobs. You may assume no release times.
Now formulate an integer program for the minimum weighted completion time using the second method in the notes (ie. variables x_ij for jobs i and j ).
Solve the problem using lp-solve.
Extra credit: Formulate the problem with release times. Choose some (non-trivial) release times and recompute the new optimum solution.
July 4: 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)
Exercise: Solve the problem given in the slides bb1.ppt by first branching on x_1 (not on x_2). Show the full solution tree. You can use lp_solve to solve the LPs.
Extra credit: After making the first branch, solve a fractional sub-problem by the cutting plane method (June 13)
Third report due July 11 in class and consists of exercises from June 13, 17 and July 4
July 11: We looked at computing ideal formulations and applied it to the knapsack problem.     lecture notes     lrs instructions
July 18: This lecture was replaced by June 19 lecture. However please try to attend to fill out the course evaluations.