benders decomposition: Magnanti-Wong point

 1 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 24 May '15, 10:45 H_OR 21●3 accept rate: 0%

 1 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 27 Nov '15, 04:03 Andrea T 384●4●18 accept rate: 0%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: