next up previous contents index CD CD Algorithms
Next: Vertex Cover Up: Difficult Reductions Previous: Difficult Reductions

Integer Programming

As discussed in Section gif, integer programming is a fundamental combinatorial optimization problem. It is best thought of as linear programming with the variables restricted to take only integer (instead of real) values.  

Input: A set V of integer variables, a set of inequalities over V, a maximization function f(V), and an integer B.

Output: Does there exist an assignment of integers to V such that all inequalities are true and tex2html_wrap_inline26223 ? Consider the following two examples. Suppose




A solution to this would be tex2html_wrap_inline26225 , tex2html_wrap_inline26227 . Not all problems have realizable solutions, however. For the following problem:




the maximum value of f(v) is tex2html_wrap_inline26231 (given the constraints), and so there can be no solution to the associated decision problem.

We show that integer programming is hard using a reduction from 3-SAT. For this particular reduction, general satisfiability would work just as well, although usually 3-SAT makes reductions easier.

In which direction must the reduction go? We want to prove integer programming that is hard, and we know that 3-SAT is hard. If I could solve 3-SAT using integer programming and integer programming were easy, this would mean that satisfiability would be easy. Now the direction should be clear; we have to translate 3-SAT into integer programming.

What should the translation look like? Every satisfiability instance contains Boolean (true/false) variables and clauses. Every integer programming instance contains integer variables (values restricted to 0,1,2,...) and constraints. A reasonable idea is to make the integer variables correspond to Boolean variables and have constraints serve the same role as the clauses do in the original problem.

Our translated integer programming problem will have twice as many variables as the SAT instance, one for each variable and one for its complement. For each variable tex2html_wrap_inline26233 in the set problem, we will add the following constraints:

For each clause tex2html_wrap_inline26249 in the 3-SAT instance, construct a constraint: tex2html_wrap_inline26251 . To satisfy this constraint, at least one the literals per clause must be set to 1, thus corresponding to a true literal. Satisfying this constraint is therefore equivalent to satisfying the clause.

The maximization function and bound prove relatively unimportant, since we have already encoded the entire 3-SAT instance. By using tex2html_wrap_inline26253 and B=0, we ensure that they will not interfere with any variable assignment satisfying all the inequalities. Clearly, this reduction can be done in polynomial time. To establish that this reduction preserves the answer, we must verify two things:

The reduction works both ways, so integer programming must be hard. Notice the following properties, which hold true in general for NP-complete:

next up previous contents index CD CD Algorithms
Next: Vertex Cover Up: Difficult Reductions Previous: Difficult Reductions

Mon Jun 2 23:33:50 EDT 1997