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 ?

Example:

A solution to this is , .

Example:

Since the maximum value of f(v) given the constraints is , 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 in the set problem, we will add the following constraints:

• and

  Both IP variables are restricted to values of 0 or 1, which makes them equivalent to boolean variables restricted to true/false.

• 

  Exactly one of the IP variables associated with a given sat variable is 1. This means that exactly one of and are true!

• for each clause in the sat instance, construct a constraint:

  

  Thus at least one IP variable must be one in each clause! Thus satisfying the constraint is equivalent to satisfying the clause!

Our maximization function and bound are relatively unimportant: 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 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 NP, since the numbers assigned to the variables may be too large to write in polynomial time - don't be too hasty!