6
$\begingroup$

I was following Wolsey Example 9.3: Let $X = \{(x,y) \in (R^{m}_+,B^1) : \sum_{i=1}^m x_i \leq my\}$. Now consider the valid inequality $x_i \leq y$ and show that it is facet defining.

My question is why is this a valid inequality? For example one point in $X$ may be $(x,y) = ((0,3,0),(1))$ such that $0+3+0 \leq 3\times1$, but their valid inequality removes this solution, $3 \leq 1$.

$\endgroup$
5
  • $\begingroup$ Although it is not explicitely written, I believe $x_i \le 1$. $\endgroup$
    – Kuifje
    Sep 26, 2022 at 10:26
  • $\begingroup$ @Joshua, Are you sure the valid inequality $x_i \leq y$ would not be $x_i \leq M*y$? $\endgroup$
    – A.Omidi
    Sep 26, 2022 at 10:44
  • $\begingroup$ @Omidi That would makes sense to me, but it is not what is written in the book. $\endgroup$
    – Joshua
    Sep 26, 2022 at 14:28
  • $\begingroup$ @Kuifje Do you know why it would be implied? Never the less, if I assumed that, the rest of the example would make sense. $\endgroup$
    – Joshua
    Sep 26, 2022 at 14:30
  • $\begingroup$ @Joshua I assumed that because with such binaries, $X$ describes part of the facility location problem. $\endgroup$
    – Kuifje
    Sep 27, 2022 at 8:00

1 Answer 1

12
$\begingroup$

As @Kuifje suggested, an upper bound $x_i \le 1$ was mistakenly omitted. This omission was noted in this errata sheet, and it was corrected in the second edition of the book.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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