Valid Inequality Example (Wolsey Example 9.3)

Question

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$.

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

RobPratt · Answer 1 · 2022-09-26T15:46:32.740

12

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.

edited Sep 26 '22 at 15:46

answered Sep 26 '22 at 14:27

RobPratt

32,006
1
44
84

Valid Inequality Example (Wolsey Example 9.3)

1 Answers1