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$
  • 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 '17 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 '17 at 3:50
  • $\begingroup$ @Eugene Make an answer? By the way, exactly the same trick is used in one of my papers. $\endgroup$ – Yuval Filmus Oct 13 '17 at 12:45
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, privacy policy and cookie policy

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