Proving 0-1 integer programming is NP-complete (using reduction from 3-CNF-SAT)

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[1]). We will follow the template given in an earlier post.

Problem statement

The decision problem for 0-1 integer programming is formulated as follows[2]:

Given an integer m \times n matrix A and an integer m-vector b, determine whether there exists an integer n-vector x with elements in \{0, 1\}, such that:

(1)   \begin{equation*}Ax \le b\end{equation*}

Note: For vectors u, v ~:~ u \le v \iff all elements in u are element-wise less than or equal to all elements in v.

Showing the problem is in NP

Let the certificate be vector x. Ax can be computed in \mathcal{O}(nm). Finally, elementwise comparison of Ax and b can be performed in \mathcal{O}(m) to determine if Ax \le b. 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:

(2)   \begin{equation*}\textsc{3-CNF-SAT} \le_\text{P} \textsc{0-1-Integer-Programming}\end{equation*}

Reduction

For 3-CNF formula \Phi, containing v variables and c clauses, construct c \times v matrix A such that:

(3)   \begin{equation*}a_{i, j} =\begin{cases}-1~&\text{if variable \textit{j} occurs \textbf{only without negation} in clause \textit{i}}\\1~&\text{if variable \textit{j} occurs \textbf{only with negation} in clause \textit{i}}\\0~&\text{otherwise}\end{cases}\end{equation*}

Also, construct c-vector b such that:

(4)   \begin{equation*}b_i = -1 + \sum_{j=1}^v \max(0, a_{i, j})\end{equation*}

In other words: b_i = -1 + the number of negated literals in clause i.

We observe that A and c can be constructed in \mathcal{O}(cl), proving that the reduction can be done in polynomial time.

We will now prove that the existence of c-vector x : Ax \le b \iff \Phi is satisfiable. Consider vector x to represent an assignment of the variables in \Phi, where:

(5)   \begin{equation*}x_i = \begin{cases}1~&\text{if variable \textit{i} is assigned \textsc{True}}\\0~&\text{if variable \textit{i} is assigned \textsc{False}}\end{cases}\end{equation*}

Let y = Ax. From Equations 1, 3 and 4:

(6)   \begin{equation*}y_i \leq b_i \iff  \text{sum of satisfied literals in clause \textit{i}} \geq 1 \iff  \text{clause \textit{i} is satisfied}\end{equation*}

From Equation 6 and the definition of the \leq operator

(7)   \begin{equation*}y = Ax \leq b \iff x~\text{is an assignment satisfying}~\Phi \qquad \blacksquare\end{equation*}

Example

(8)   \begin{equation*}\Phi = (x_1 \lor x_2 \lor \lnot x_3) \land (x_1 \lor x_3 \lor x_4) \land (\lnot x_2 \lor \lnot x_3 \lor \lnot x_4) \end{equation*}

Our reduced instance looks as follows (zeroes omitted):

(9)   \begin{equation*}\begin{bmatrix}-1 & -1 & 1  &     \\-1 &      & -1& -1 \\     &  1  &  1 & 1   \end{bmatrix}\times\begin{bmatrix}x_1\\x_2\\x_3\\x_4\end{bmatrix}\le\begin{bmatrix}0\\-1\\2\end{bmatrix}\end{equation*}

We can see that \langle x_1 = \text{T}, x_2 = \text{F}, x_3 = \text{F}, x_4 = \text{F}\rangle satisfies \Phi and that

(10)   \begin{equation*} \begin{bmatrix} -1 & -1 & 1 & \\ -1 & & -1& -1 \\ & 1 & 1 & 1 \end{bmatrix} \times \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix}=\begin{bmatrix} -1\\ -1\\ 0 \end{bmatrix} \le \begin{bmatrix} 0\\ -1\\ 2 \end{bmatrix} \end{equation*}

  1. [1]
    R. M. Karp, “Reducibility among Combinatorial Problems,” in Complexity of Computer Computations, Springer US, 1972, pp. 85–103.
  2. [2]
    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.