In this post, we will prove that 0-1 integer programming is NP-complete using a reduction from 3-CNF-SAT (which is NP-complete). We will follow the template given in an earlier post.
The decision problem for 0-1 integer programming is formulated as follows:
Given an integer matrix and an integer -vector , determine whether there exists an integer -vector with elements in , such that:
Note: For vectors all elements in are element-wise less than or equal to all elements in .
Showing the problem is in NP
Let the certificate be vector . can be computed in . Finally, elementwise comparison of and can be performed in to determine if . This proves a certificate for the problem can be verified in polynomial time.
Showing the problem is NP-hard
We will show that the problem is NP-hard by showing:
For 3-CNF formula , containing variables and clauses, construct matrix such that:
Also, construct -vector such that:
In other words: the number of negated literals in clause .
We observe that and can be constructed in , proving that the reduction can be done in polynomial time.
We will now prove that the existence of -vector is satisfiable. Consider vector to represent an assignment of the variables in , where:
From Equation 6 and the definition of the operator
Our reduced instance looks as follows (zeroes omitted):
We can see that satisfies and that
- R. M. Karp, “Reducibility among Combinatorial Problems,” in Complexity of Computer Computations, Springer US, 1972, pp. 85–103.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.