# Partial linear relaxation yields an integer solution

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.

• You have not defined $N_i$. I suspect that is a rather key aspect. And I assume the relaxation is $0 \leq x_i \leq 1$? – Michael Grant May 14 '13 at 0:40
• Sorry for the lack of precision. This is a maximal covering location problem and $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_j$ is incurred. – user77571 May 14 '13 at 1:00
• Furthermore: can one make any assumptions about the signs of $f_i$ and/or $c_j$ (e.g., are they positive? nonnegative?) I recommend editing the question itself with these clarifications. – Michael Grant May 14 '13 at 1:01
• Thanks for the suggestion -- I edited the question. – user77571 May 14 '13 at 1:18

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.