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).

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×nm \times n matrix AA and an integer mm-vector bb, determine whether there exists an integer nn-vector xx with elements in {0,1}\{0, 1\}, such that:

Ax≤b Ax \le b Note: We define ≤\le for vectors u,vu, v with length nn as u≤v  ⟺  ∀i:1≤i≤n:ui≤viu \le v \iff \forall i : 1 \le i \le n: u_i \le v_i. In other words, uu is element-wise less or equal to vv.

Showing the problem is in NP

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

3-CNF-SAT≤P0-1-Integer-Programming \text{3-CNF-SAT} \le_\text{P} \text{0-1-Integer-Programming}

Reduction

For 3-CNF formula Φ\Phi, containing vv variables and cc clauses, construct c×vc \times v matrix AA such that:

ai,j={−1 if variable j occurs only without negation in clause i1 if variable j occurs only with negation in clause i0 otherwise 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 cc-vector bb such that:

bi=−1+∑j=1vmax⁡(0,ai,j) b_i = -1 + \sum_{j=1}^v \max(0, a_{i, j})

In other words: bi=−1 b_i = -1~ plus the number of negated literals in clause ii.

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

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

xi={1 if variable i is assigned True0 if variable i is assigned False 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=Axy = Ax, then:

yi≤bi  ⟺  sum of satisfied literals in clause i≥1  ⟺  clause i is satisfied 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≤b  ⟺  x is an assignment satisfying Φ 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:

Φ=(x1∨x2∨¬x3)∧(x1∨x3∨x4)∧(¬x2∨¬x3∨¬x4) \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):

[−1−11−1−1−1111]×[x1x2x3x4]≤[0−12] \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 ⟨x1=T,x2=F,x3=F,x4=F⟩\langle x_1 = \text{T}, x_2 = \text{F}, x_3 = \text{F}, x_4 = \text{F}\rangle satisfies Φ\Phi and that

[−1−11−1−1−1111]×[1000]=[−1−10]≤[0−12] \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}