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's gravatar image

H_OR
213
accept rate: 0%

edited 24 May '15, 10:48


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

link

answered 27 Nov '15, 04:03

Andrea%20T's gravatar image

Andrea T
384418
accept rate: 0%

edited 27 Nov '15, 04:10

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×9
×6
×3

Asked: 24 May '15, 10:45

Seen: 757 times

Last updated: 27 Nov '15, 04:10

OR-Exchange! Your site for questions, answers, and announcements about operations research.