0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$? $\endgroup$ – Michael Grant May 14 '13 at 0:40
  • $\begingroup$ 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. $\endgroup$ – user77571 May 14 '13 at 1:00
  • $\begingroup$ 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. $\endgroup$ – Michael Grant May 14 '13 at 1:01
  • $\begingroup$ Thanks for the suggestion -- I edited the question. $\endgroup$ – user77571 May 14 '13 at 1:18
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Many thanks for your answer! $\endgroup$ – user77571 May 16 '13 at 16:46

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.