Bland rule proof linear programming

[bhobba]

Can I ask what is your objective here?

Do you want to understand a specific proof of the Bland Rule or are you after understanding the Bland Rule itself?

If the former be aware people that write textbooks, articles, papers etc are human like the rest of us and make mistakes. When I did my degree there were often mistakes in the lectures, problems sets etc. I remember one of the first subjects I did - Calculus and Analysis A had the wrong answer of a problem. I worked through it time and time again using all sorts of different approaches - I got my answer each time. The lecturers answer was wrong. At the next tutorial he said - its can't be wrong - I have been using the same tutorials for years and nobody ever bought a mistake to my attention. He went though it with me and lo and behold - it was wrong. Since then I have had many such experiences - some where I had to find the correct answer myself. In many of my classes I was told anybody that spots a mistake I made in the material will instantly pass. I usually found a number. I asked one lecturer - why do you do it. He laughed and said anyone good enough to spot mistakes will pass anyway - likely get an honor - so it was just a challenge to good students.

You are obviously having trouble with this - but an internet search on 'bland rule proof' brings back a number of hits. Why not try to understand some of those first then come back to your proof?. It may be the proof you have is wrong or missing important details. That's what I would do. I often read papers and come across issues I need to nut out - only rarely do I need somebody else's help - I do an internet search, look in my personal library, even make the rather lengthy trip to my old Alma Mata and use their library which as an ex student I am allowed to do. It is in a middle of Brisbane and parking is murder - but if I have to do it, I have to do it.

I don't know if this is post-grad or undergrad. If undergrad get your lecturer to help. If post-grad it 's all part of post-grad - you are expected to do this yourself - same if you are studying it simply for pleasure/interest - it's part and parcel of this learning thing.

Here we generally prefer to give hints - you learn better that way. As they say - give a man a fish and he eats for one meal - teach him how to fish and he never starves. Same here. Of course if required we will explicitly give the answer - if we can - you have picked an area that not many regulars know much about. But please, do what I suggest and post back with how you went.

Thanks
Bill

 

[Ray Vickson]

Actually I do not try to deviate from or stray away from the main discussion, just eager to comprehend the proof. Also MENTORS of forum suggest me to create thread here(@fresh_42, @bhobba ...) about that question. I have only 1 LEFT QUESTION :

you can easily see objective value change with new set of solution is $c_s$*q(xs) on left hand side of equation $\upsilon+c_sq = \upsilon+c^*_sq + \sum_{x_k \in B_i} c^*_k\left(b_k-a_{ks}q\right)$ I got it , BUT I can not understand why the objective change on the right hand side of previous equation is $c^*_sq + \sum_{x_k \in B_i} c^*_k\left(b_k-a_{ks}q\right)$?? WHY do we multiply $c^*_s$ with xs(q) or $c^*_k$ with $b_k-a_{ks}*q$ TO UPDATE OBJECTIVE??
Please @tnich @Ray Vickson I am waiting your help...

Okay, I will relent this once and continue to reply.

The presentation of Bland's rule proof you gave in your link is mostly the same as the one on pages 37--38 of the book "Linear Programming", by Vasek Chvatal, but with some aspects missing.

First, the actual Bland rule involves using the smallest subscript rule for both entering and leaving variables, but your attachment talks about entering variables only; however, maybe in the lectures this was discussed more fully.

Next, your attachment has variable $x_t$ leaving in some dictionary D but entering again in some other dictionary D*, and for that to happen we may need more than one "cycle". That is, we might not have $x_t$ leave and then re-enter in the sequence of dictionaries $D_0, D_1, \ldots D_k = D_0$. For example, $x_t$ may be non-basic in $D_0$, then enter at some $D_p$ then leave again at some $D_q > D_p$, never to enter again before $D_k$. The cited document does not account for such a case.

The argument of Chvatal gets around this potential problem by noting that if we always apply the same rules and get cycling, then the extended sequence $D_0, D_1, \ldots, D_k (= D_0) , D_1, D_2, \ldots$ will always be obtained and it will always contain a subsequence in which $x_t$ leaves in one $D$ and enters again in some later $D*$. Then the arguments given in your cited document go through, and are essentially a copy of the arguments given by Chvatal.

Finally, I will say that if you Google the keywords "Bland's rule" you will see many different proofs of the rule. If you are having trouble following one proof, nothing is stopping you from going on-line to look at other proofs.

 

[mertcan]

Okay, I will relent this once and continue to reply.

The presentation of Bland's rule proof you gave in your link is mostly the same as the one on pages 37--38 of the book "Linear Programming", by Vasek Chvatal, but with some aspects missing.

First, the actual Bland rule involves using the smallest subscript rule for both entering and leaving variables, but your attachment talks about entering variables only; however, maybe in the lectures this was discussed more fully.

Next, your attachment has variable $x_t$ leaving in some dictionary D but entering again in some other dictionary D*, and for that to happen we may need more than one "cycle". That is, we might not have $x_t$ leave and then re-enter in the sequence of dictionaries $D_0, D_1, \ldots D_k = D_0$. For example, $x_t$ may be non-basic in $D_0$, then enter at some $D_p$ then leave again at some $D_q > D_p$, never to enter again before $D_k$. The cited document does not account for such a case.

The argument of Chvatal gets around this potential problem by noting that if we always apply the same rules and get cycling, then the extended sequence $D_0, D_1, \ldots, D_k (= D_0) , D_1, D_2, \ldots$ will always be obtained and it will always contain a subsequence in which $x_t$ leaves in one $D$ and enters again in some later $D*$. Then the arguments given in your cited document go through, and are essentially a copy of the arguments given by Chvatal.

Finally, I will say that if you Google the keywords "Bland's rule" you will see many different proofs of the rule. If you are having trouble following one proof, nothing is stopping you from going on-line to look at other proofs.

Can I ask what is your objective here?

Do you want to understand a specific proof of the Bland Rule or are you after understanding the Bland Rule itself?

If the former be aware people that write textbooks, articles, papers etc are human like the rest of us and make mistakes. When I did my degree there were often mistakes in the lectures, problems sets etc. I remember one of the first subjects I did - Calculus and Analysis A had the wrong answer of a problem. I worked through it time and time again using all sorts of different approaches - I got my answer each time. The lecturers answer was wrong. At the next tutorial he said - its can't be wrong - I have been using the same tutorials for years and nobody ever bought a mistake to my attention. He went though it with me and lo and behold - it was wrong. Since then I have had many such experiences - some where I had to find the correct answer myself. In many of my classes I was told anybody that spots a mistake I made in the material will instantly pass. I usually found a number. I asked one lecturer - why do you do it. He laughed and said anyone good enough to spot mistakes will pass anyway - likely get an honor - so it was just a challenge to good students.

You are obviously having trouble with this - but an internet search on 'bland rule proof' brings back a number of hits. Why not try to understand some of those first then come back to your proof?. It may be the proof you have is wrong or missing important details. That's what I would do. I often read papers and come across issues I need to nut out - only rarely do I need somebody else's help - I do an internet search, look in my personal library, even make the rather lengthy trip to my old Alma Mata and use their library which as an ex student I am allowed to do. It is in a middle of Brisbane and parking is murder - but if I have to do it, I have to do it.

I don't know if this is post-grad or undergrad. If undergrad get your lecturer to help. If post-grad it 's all part of post-grad - you are expected to do this yourself - same if you are studying it simply for pleasure/interest - it's part and parcel of this learning thing.

Here we generally prefer to give hints - you learn better that way. As they say - give a man a fish and he eats for one meal - teach him how to fish and he never starves. Same here. Of course if required we will explicitly give the answer - if we can - you have picked an area that not many regulars know much about. But please, do what I suggest and post back with how you went.

Thanks
Bill

I think you should first do the simplex pivots with $x_s=0$. Then start again with $x_s=q$ to see how things change.

I suggest that you follow the author's plan: write out a tableau with a degenerate solution, pivot to bring one of the fickle variables $x_s$ into the basis, set $x_s=q$, and then perform a pivot to bring a new fickle variable into the basis. See what you get. Then compare your result with $\upsilon+c_sq = \upsilon+c^*_sq + \sum_{x_k \in B_i} c^*_k\left(b_k-a_{ks}q\right)$.

Initially, thanks for your attention, not being relentless...I have been suffocating in that problem for 2 months, I strived for digging something valuable out of internet but I encountered the same proof related to Bland rule( I bet you can not find different kind of proof about that either, ALL PROOFS ARE SAME believe me ), so I decided to discuss my problem with you, did not created a thread as soon as I had a problem, also I already have the Chavatal book by the way I will present the CONTRADICTION about the proof even in Chavatal, thus I would like to share 2 different screenshot from Chavatal:
In the picture 1 he updates the non basic variable $x_s$ with a some number "t" and according to new value of $x_s$ he also updates 2 different dictionaries. I totally agree what he did in picture 1.
BUT IN PICTURE 2, he again updates the non basic variable $x_s$ with a some number y ( it was "t" in picture 1, nothing different ), while everything is going as I want then he adds the equation in the RED BOX which is $\sum_{i\in B} c^*_i\left(b_i-a_{is}y\right)$. Why he adds RED BOX??

He also expresses in GREEN BOX that the equation in ORANGE BOX which is $z = \upsilon+ \sum_{j=1} c^*_jx_j$ obtained from algebraic MANIPULATIONS. WHAT is this ALGEBRAIC MANIPULATION??

I think there is an impasse, mystery...

 

[tnich]

Initially, thanks for your attention, not being relentless...I have been suffocating in that problem for 2 months, I strived for digging something valuable out of internet but I encountered the same proof related to Bland rule( I bet you can not find different kind of proof about that either, ALL PROOFS ARE SAME believe me ), so I decided to discuss my problem with you, did not created a thread as soon as I had a problem, also I already have the Chavatal book by the way I will present the CONTRADICTION about the proof even in Chavatal, thus I would like to share 2 different screenshot from Chavatal:
In the picture 1 he updates the non basic variable $x_s$ with a some number "t" and according to new value of $x_s$ he also updates 2 different dictionaries. I totally agree what he did in picture 1.
BUT IN PICTURE 2, he again updates the non basic variable $x_s$ with a some number y ( it was "t" in picture 1, nothing different ), while everything is going as I want then he adds the equation in the RED BOX which is $\sum_{i\in B} c^*_i\left(b_i-a_{is}y\right)$. Why he adds RED BOX??

He also expresses in GREEN BOX that the equation in ORANGE BOX which is $z = \upsilon+ \sum_{j=1} c^*_jx_j$ obtained from algebraic MANIPULATIONS. WHAT is this ALGEBRAIC MANIPULATION??

I think there is an impasse, mystery...

Once again, I suggest that you mechanically work through the pivots and see what you get.