Statement

Proof

We are going to find a Many-one reduction of Max-SAT to integer linear programming (ILP). Which as Max-SAT is NP-hard will give us integer linear programming is too.

Suppose we have an instance of the Max-SAT problem given by $f$. Design an ILP with the variables $y_i$ for each $x_i$ variable in $f$ (with $1 \leq i \leq n$) and $z_j$ for each $c_j$ clause in $f$ (with $1 \leq j \leq m$).

Now add the following constraints,

$$ 0 \leq y_i \leq 1, \mbox{ and } 0 \leq z_j \leq 1 $$

this will relate to the variables $x_i$ and clauses $c_j$ being true or false.

To add constraints to reflect the clauses $c_j$ suppose $c_j$ contains positive literals involving variables $c_j^+ := \{i \vert x_i \in c_j\}$ and negative literals $c_j^- = \{i \vert \overline{x_i} \in c_j\}$. So we have the clause

$$ c_j = \left ( \bigvee_{i \in c_j^+} x_i \right ) \lor \left ( \bigvee_{i \in c_j^-} \overline{x_i} \right). $$

For each clause $c_j$ add the following constraint

$$ \sum_{i \in c_j^+} y_i + \sum_{i \in c_j^-} (1 - y_i) \geq z_j $$

this guarantees for integer points $z_j$ can only be 1 if $x_i = 1$ for some $i \in c^+_j$ or $x_i = 0$ for some $i \in c^-_j$.

Lastly to define the reduction, we need to define the objective function

$$\max \sum_{j=1}^m z_j.$$

This reduction takes time $O(mn)$, as we need to go through each clause to convert them into functionals. So this takes polynomial time.

When provided with a solution to the ILP return the solution to the Max-SAT problem with $x_i$ true for all $y_i = 1$ and $x_i$ false for all $y_i = 0$. This takes $O(n)$ time so takes polynomial time.

Let $v$ be the max value of the constructed ILP and $w$ be the max value of Max-SAT. From Claim 1 we have $w \leq v$. Equally Claim 2 gives us $v \leq w$. This provides that $v = w$ and we have the solution of the contracted ILP if and only if we have a solution to the Max-SAT problem.

Claim 1

Proof of Claim 1

Set $y_i = a(x_i)$ and $z_j = a(c_j)$, 1 if true and 0 if false. This satisfies the bounds on the variables and they are integers. The clause constraint

$$ \sum_{i \in c_j^+} y_i + \sum_{i \in c_j^-} (1 - y_i) \geq z_j $$

is satisfied as if there is a literal making $c_j$ true the corresponding value of $y_i$ or $(1-y_i)$ is 1 allowing $z_j$ to be 1.

The objective function

$$\sum_{j=1}^m z_j$$

is the number of satisfied clauses by definition.

Claim 2

Proof of Claim 2

We set $a(x_i) = y_1$ with $1$ being True and $0$ being False. The clause constraint

$$ \sum_{i \in c_j^+} y_i + \sum_{i \in c_j^-} (1 - y_i) \geq z_j $$

guarantees that if this assignment doesn’t satisfy $c_j$ then $z_j = 0$ as $0 \leq z_j \leq 1$ and

$$ \sum_{i \in c_j^+} y_i + \sum_{i \in c_j^-} (1 - y_i) = \sum_{i \in c_j^+} 0 + \sum_{i \in c_j^-} (1 - 1) = 0 \geq z_j. $$

Therefore

$$ \sum_{j = 1}^m z_j \leq \sum_{j=1}^m a(c_j) $$

and we get the required statement.