next up previous index CD Book Algorithms
Next: Lecture 21 - vertex Up: No Title Previous: Lecture 19 - satisfiability

Lecture 20 - integer programming

Listen To Part 22-6

36.4-5 Give a polynomial-time algorithm to satisfy Boolean formulas in disjunctive normal form.  

Satisfying one clause in DFS satisfied the whole formula. One clause can always be satisfied iff it does not contain both a variable and its complement.

Why not use this reduction to give a polynomial-time algorithm for 3-SAT? The DNF formula can become exponentially large and hence the reduction cannot be done in polynomial time.

Listen To Part 24-2

A Perpetual Point of Confusion

Note carefully the direction of the reduction.  

We must transform every instance of a known NP-complete problem to an instance of the problem we are interested in. If we do the reduction the other way, all we get is a slow way to solve x, by using a subroutine which probably will take exponential time.

This always is confusing at first - it seems bass-ackwards. Make sure you understand the direction of reduction now - and think back to this when you get confused.

Listen To Part 24-3

Integer Programming

Instance: A set v of integer variables, a set of inequalities over these variables, a function f(v) to maximize, and integer B.  

Question: Does there exist an assignment of integers to v such that all inequalities are true and tex2html_wrap_inline15937 ?





A solution to this is tex2html_wrap_inline15939 , tex2html_wrap_inline15941 .





Since the maximum value of f(v) given the constraints is tex2html_wrap_inline15945 , there is no solution.

Theorem: Integer Programming is NP-Hard

Proof: By reduction from Satisfiability

Any set instance has boolean variables and clauses. Our Integer programming problem will have twice as many variables as the SAT instance, one for each variable and its compliment, as well as the following inequalities:

Listen To Part 24-4

For each variable tex2html_wrap_inline15947 in the set problem, we will add the following constraints:

Our maximization function and bound are relatively unimportant: tex2html_wrap_inline15961 B=0.

Clearly this reduction can be done in polynomial time.

Listen To Part 24-5

We must show:

  1. Any SAT solution gives a solution to the IP problem.

    In any SAT solution, a TRUE literal corresponds to a 1 in the IP, since if the expression is SATISFIED, at least one literal per clause in TRUE, so the sum in the inequality is tex2html_wrap_inline15965 1.

  2. Any IP solution gives a SAT solution.

    Given a solution to this IP instance, all variables will be 0 or 1. Set the literals correspondly to 1 variable TRUE and the 0 to FALSE. No boolean variable and its complement will both be true, so it is a legal assignment with also must satisfy the clauses.

Neat, sweet, and NP-complete!

Listen To Part 24-6

Things to Notice

  1. The reduction preserved the structure of the problem. Note that the reduction did not solve the problem - it just put it in a different format.
  2. The possible IP instances which result are a small subset of the possible IP instances, but since some of them are hard, the problem in general must be hard.
  3. The transformation captures the essence of why IP is hard - it has nothing to do with big coefficients or big ranges on variables; for restricting to 0/1 is enough. A careful study of what properties we do need for our reduction tells us a lot about the problem.
  4. It is not obvious that IP tex2html_wrap_inline15969 NP, since the numbers assigned to the variables may be too large to write in polynomial time - don't be too hasty!

next up previous index CD Book Algorithms
Next: Lecture 21 - vertex Up: No Title Previous: Lecture 19 - satisfiability

Mon Jun 2 09:21:39 EDT 1997