Integer Programming

As discussed in Section , 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 ? Consider the following two examples. Suppose

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

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

• To restrict each integer programming variable to values of 0 or 1, we add constraints and . Thus they correspond to values of and .
• To ensure that exactly one of the two integer programming variables associated with a given SAT variable is , add constraints so that .

For each clause in the 3-SAT instance, construct a constraint: . 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 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:

• Any SAT solution gives a solution to the IP problem - In any SAT solution, a literal corresponds to a 1 in the integer program, since the clause is satisfied. Therefore, the sum in each clause inequality is .
• Any IP solution gives a SAT solution - In any solution to this integer programming instance, all variables must be set to either 0 or 1. If , then set literal . If , then set literal . No Boolean variable and its complement can both be true, so it is a legal assignment, which must also satisfy all the clauses.

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

• The reduction preserved the structure of the problem. It did not solve the problem, just put it into a different format.
• The possible IP instances that can result from this transformation are only a small subset of all possible IP instances. However, since some of them are hard, the general problem must be hard.
• The transformation captures the essence of why IP is hard. It has nothing to do with having big coefficients or big ranges on variables; since restricting them to 0/1 is enough. It has nothing to do with having inequalties with large numbers of variables. Integer programming is hard because satisfying a set of constraints is hard. A careful study of the properties needed for a reduction can tell us a lot about the problem.