Reports and Grading
Computational Intractability
Spring 2011
also check:
announcements
return to: course home page
1. The course grade is based on 3
reports with due dates: Thurs.
May
12, Thurs. June 16, Thurs. July 14 in class.
2. Each report will be graded pass/fail.
3. Final grades: A: 3 passes, B: 2 passes, C: 1
pass, No Credit: 0 passes.
4. S grade will be given for student who gets an A and also solves optional bonus problems.
5. Reports will be based on exercises given in class, which will be
posted on this web page.
Teaching Assistant:
Atsuki
Nagao
a-nagao
at
lab2.kuis.kyoto-u.ac.jp
Third
Report
Due
July
14
in
class
All
problems are
now included.
June 16: Read the lecture notes
on crew scheduling. For the example in the notes, explain how the
company can use only two flight crews
if they reschedule two
existing flights.
Draw the new flight graph, flight connection graph, formulate the LP
and use lp_solve to solve it.
Do you get an integer solution from the LP formulation without
specifying integer variables?
June 23: Solve the following
problem by hand using the dual
simplex method. Show all steps, and verify the optimal solution
by duality.
How does this problem relate to the problem in the notes
from the May 12 lecture?
max -5x1 -3x2
s.t. -x1 -x2 <= -5
-2x1 -x2 <= -6
-3x1 -2x2 <= -9
x1, x2 >= 0
June 30: Read the class notes.
Use the precedence diagram on page 1
of the notes, and randomly assign processing times of either 1 or 2
units to each job.
Also randomly assign release
times and weights wj from the set {1,2,3,4,5} to each job.
Now formulate the problem of finding
the minimum weight sum of completion times as an integer linear
program, using either of the
formulations in the notes.
Solve the problem using lp_solve.
Give the solution of the linear programming relaxation, and also the
solution of the integer program (it may take quite a long time for
lp_solve to terminate)
Report the two solutions, and the
time taken to get each.
Bonus
problem: Formulate your problem using both methods in the notes, and
compare the solutions and running times.
Second
Report Due June
16 All problems are
now included.
May 12: Simplex Method.
Do exercise 2.2, P. 26, from
the handout
LP_en.pdf . First solve the
problem by
hand using the dictionary method. Then analyze the final dictionary to
find all optimum solutions. Hint: To find a different optimum
solution you should pivot using a term with zero coefficient in the
optimum dictionary (Why?)
May 26: Refer to Fukuda's
cycling example in the class notes.
Firstly compute the complete cycle and list out the index sets B and N
for each iteration.
Next sketch the three dimensional region for the problem (note that it
is unbounded, in fact it is a cone).
Notice that the cone has 6 inequalities, three given in the starting
dictionary plus 3 nonnegativity inequalities: x1,x2,x3 >= 0.
This defines 6 faces of the cone.
By making copies of your sketch, show the series of pivots by shading
the three faces corresponding to the cobasic(ie. RHS in the dictionary)
variables.
June 2:
(a) Prove the the dual of the dual is the primal. Hint: First put the
dual in the same format as the primal (ie max cx, Ax <= b, x>=0)
(b) Construct your own
example an LP with at least 2 variables and two constraints for
which both the primal and dual are infeasible.
(c) 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.
First
Report Due May
12. All problems are
now included.
April 14:
Depot Location
Problem.
Data: N=number of regions,
pi = population of
region i, M=number of possible depot locations, cij=time
to
deliver
to
region
i
from
depot
j,
k=number
of
depots to open
Problem: A delivery company wants to
choose k locations for depots from
the M candidate locations.
Region i can be served by depot j if
the delivery time cij
is at most 30 minutes.
Decide which k depots the company
should open in order to maximize the
population served by at least one depot.
Formulate this problem as an integer
program.
Construct a small example with N=6,
M=6, k=2 and with pi and
cij random integers between 10 and 60. Solve
using lp_solve
software. (See announcements
for details)
April 21:
1. Prove that 3-SAT is reducible to
4-SAT.
2. Modify the construction given in
class and in the slides to
show directly that 4-SAT is reducible to
Directed Hamiltonian Cycle.
April 28:
1. Do a direct reduction from
3SAT to Partition by making a
simple modification of the method we studied in class
(Partition: Can positive integers a1,
a2, ..., an be split into two
equal weight subsets?)
2. Supply a proof of correctness for
your answer to question 1.
Optional Bonus
Problem: Consider
the sushi problem with n pieces of sushi. A piece of sushi costs at
most 1000 yen, and receives a score of between zero and 100 points.
You have N yen available and want to
maximize your score. Show how to
solve this problem in time polynomial in n.