Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I \notag \\ &x_j, y_i \in \{0,1\} \notag \\ \end{align} where $f_i,c_i\ge0$. How do I prove that a linear relaxation of only $x$ variables (i.e. $x_j\ge0$) yields a binary solution? Any suggestion is greatly appreciated.
Note: This is a maximal covering location problem, where $N_i$ is a set of nodes. So, if at least one facility is located in $N_i$ (i.e. $\sum _{j \in N_i} x_j \ge 1$), node $i$ is considered covered (i.e. $y_i=0$). Otherwise, a cost $c_i$ is incurred.
This doesn't seem to be true.
Take $|I| = |J| = 3$, and pick three neighbourhoods, namely $\{1,2\}, \{1, 3\},$ and $\{2,3\}$. Take $c_i = 50$ for all $i$ and $f_i = 1$ for all $i$.
The optimal solution if we let $x$ be fractional is $x = (\frac12, \frac12, \frac12)$, $y = (0, 0, 0)$, which has objective value $1.5$. You can check that, if $x$ and $y$ must both be integral, the optimal solution has objective value $2$.
EDIT: However, for a fixed integral $x$, it is quite easy to find an optimal $y$; set $y_i$ to 1 whenever $c_i$ is negative or the corresponding constraint would otherwise be violated; set $y_i$ to zero otherwise.