Hi, I studied "Practical enhancements to the Magnanti-Wong method" in which the author developed a very cool modification of Magnanti-Wong benders cut. However, Theorem 7 of the paper that explains how we can generate Magnanti-Wong point is not clear to me. I will state the Theorem here for convenience: Theorem 7. If cone (b − Y ) ⊇ Y −y0, U # ∅, and there is an x0 ≥ 0 such that Ax0 + y0 = b, then y0 is a Magnanti–Wong point. Could someone give an example how this theorem can be applied. Thank you!
asked
H_OR |

I read that paper too. The notation "\(\mathbf{b}-Y\)" where \(Y\) is a set is a bit puzzling, but as far as I understood you have two conditions: 1 dual feasibility, given by constraints \(A x_0 + y_0 = n\) and \(U \not = \emptyset\). \(U\) is the domain of the dual variables 2 spanning, given by condition \(cone(b-Y) \supseteq Y - y_0\) On the second condition \(cone(\mathbf{b}-Y)\) represent the set of vectors spanned by non-negative linear combinations of \(b-Y\). Now, I interpret \(b-Y\) as the set \(\{w \in R^n| \exists y\in Y s.t. \mathbf{b}-y = w\}\). This is also the explanation given in the proof, after equation 22 So the second condition asks that all the values \((\mathbf{b}-y)\) with \(y\in Y\) can be represented ad difference between elements in \(Y\). As an example, if \(Y\subseteq \{0,1\}^n\) and \(\mathbf{b}\ge \mathbf{1}\) the condition is always verified, as it is in the computational experiment later on the paper. I had a problem instead where \(Y\) was binary and \(\mathbf{b}=0\), so I could not apply the theorem, as \(cone(\mathbf{b}-Y)\) spanned only vectors with non-positive components. Andrea
answered
Andrea T |