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.
Problem Statement
The decision problem for 0-1 integer programming is formulated as follows:
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:
\[ Ax \le b \] Note: We define \(\le\) for vectors \(u, v\) with length \(n\) as \(u \le v \iff \forall i : 1 \le i \le n: u_i \le v_i\). In other words, \(u\) is element-wise less or equal to \(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 0-1 integer programming is NP hard by showing:
\[ \text{3-CNF-SAT} \le_\text{P} \text{0-1-Integer-Programming} \]
Reduction
For 3-CNF formula \(\Phi\), containing \(v\) variables and \(c\) clauses, construct \(c \times v\) matrix \(A\) such that:
\[ a_{i, j} = \begin{cases} -1~&\text{if variable}~j~\text{occurs only without negation in clause}~i\\ 1~&\text{if variable}~j~\text{occurs only with negation in clause}~i\\ 0~&\text{otherwise} \end{cases} \]
Also, construct \(c\)-vector \(b\) such that:
\[ b_i = -1 + \sum_{j=1}^v \max(0, a_{i, j}) \]
In other words: \(b_i = -1~\) plus 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:
\[ x_i = \begin{cases} 1~&\text{if variable}~i~\text{is assigned True}\\ 0~&\text{if variable}~i~\text{is assigned False} \end{cases} \]
Let \(y = Ax\), then:
\[ y_i \leq b_i \iff \text{sum of satisfied literals in clause}~i \geq 1 \iff \text{clause}~i~\text{is satisfied} \]
From this equation:
\[ y = Ax \leq b \iff x~\text{is an assignment satisfying}~\Phi \]
Thus we have expressed a 3-CNF-SAT problem as a 0-1 integer programming problem. \(\blacksquare\)
Example
I think it’s much easier to get intuition for this reduction by looking at an example, so here it is:
\[ \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) \]
Our reduced instance looks as follows (zeroes omitted):
\[ \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} \]
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
\[ \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} \]