1
$\begingroup$

We know that 0-1 integer linear programming is NP-Hard. What about 0-1 integer linear programming with only equality constraints? If so, how to prove it

$$\min c^T x \text{ s.t. } Ax = b \quad x_i \in \{0,1\}\quad (i=1,2,...,n)$$

$\endgroup$
3
  • 1
    $\begingroup$ Hint: Try to prove it NP-hard by finding a suitable reduction partner. What NP-hard problems do you know that involve summing up some integers? $\endgroup$
    – D.W.
    Oct 13, 2017 at 2:59
  • 3
    $\begingroup$ Reduction from independent set IP where $x_i+x_j \leq 1$ can be changed to $x_i +x_j + y_{ij} = 1$, where $y_{ij}$ are auxiliary binary variables. $\endgroup$
    – Eugene
    Oct 13, 2017 at 3:50
  • $\begingroup$ @Eugene Make an answer? By the way, exactly the same trick is used in one of my papers. $\endgroup$ Oct 13, 2017 at 12:45

1 Answer 1

3
$\begingroup$

Consider the Maximum Independent Set problem ($\mathcal{NP}$-hard): given a graph $G=(V,E)$, find the maximum independent set in $G$, i.e., the subset of vertices $I \subseteq V$ such that every two vertices in $I$ are not adjacent $\forall v_1,v_2 \in I, (v_1,v_2) \notin E$.

This problem has a well known Integer programming formulation: let $x_i$ be a binary variable for every $i \in V$ and equal one if $i \in I$. \begin{align} \max & \sum\limits_{i=1}^n x_i \\ \text{subject to} & \\ & x_i + x_j \leq 1 \text{ for all } (i,j) \in E \\ & x_i \in \{0,1\} \text{ for all } i \in V \end{align}

If $|V| = n$, this problem has $n$ variables and $O(n^2)$ constraints.

To transform it to equality form (a.k.a. standard form) one might introduce slack variables for every constraint. Generally, if you have $Ax <= b$ you can write $Ax + x_s = b$ where $x_s \geq 0$ and $x_s$ are called slack variables.

It appears that for Independent Set slack variables are actually binary! Thus, you have the formulation \begin{align} \max & \sum\limits_{i=1}^n x_i \\ \text{subject to} & \\ & x_i + x_j +y_{ij} = 1 \text{ for all } (i,j) \in E \\ & x_i \in \{0,1\} \text{ for all } i \in V \\ & y_{ij} \in \{0,1\} \text{ for all } i,j \in V \end{align}

This formulation exactly satisfies yours

0-1 integer linear programming with only equality constraints (ILPEQ)

Now, you have a basic reduction argument. Suppose, you can solve ILPEQ fast, that means you can solve independent set fast, but it is known to be $\mathcal{NP}$-hard, so ILPEQ is also $\mathcal{NP}$-hard. The formal argument as well as checking that this is in fact a polynomial reduction I leave to the reader.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.