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)$$
$\begingroup$
$\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 '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
Add a comment
|
$\begingroup$
$\endgroup$
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.
