Linear programming -- Bland rule degeneracy

[mertcan]

hi, my question is related to a proof involves bland rule for avoiding the degeneracy. Initially I emphasized some sentences which have importance in attachment/file with yellow color.
At the beginning, it says xs is entering variable and when it enters objective value does not change( because all dictionaries are degenerate) which means xs will become basis and have 0 value. Afterwards it says xs=y ( y be arbitrary number), and is establishing the equation 3.10 which suits every value of y. Here my question is : Saying that xs=y ( y is arbitrary) is wisely/reasonable although it says that xs is designated to be a entering variable at first which means when it enters objective value does not change (which means xs will become basis and have 0 value)? Because later it establishes the equation 3.10 and says this equation should equal to zero for all y. But I think xs should only take 0 value because it is a entering variable at the beginning and when xs become basis it has 0 value because of the fact that objective value should not change??

I hope my question is explicit for you

 

[mertcan]

pardon, Am I explicit ?? why can not I get any answers??

 

[fresh_42]

I think we haven't many experts on linear programming among our members, so the lack of information might be a problem:
What is Bland's rule, what are dictionaries or their basis, what says theorem 3.1, what the statement, which was proven here, and what means degenerate in this context?

Beside this, many members don't like to be forced to download a document in order to read the question. Now that I downloaded it, I could upload a screen shot, but I doubt that this would change anything, as the crucial terms aren't defined there. So the way you worded the question necessarily presumes, that someone is already firm in the subject. And this excludes all, who were willing to help but don't want to search the internet for the missing information. I mean, you didn't even say nor does your pdf, what the claim is here.

 

[bhobba]

I would really like to help since I did introductory linear programming in my applied linear algebra course and one subject expanding on it in Operations Research 1A. But it wasn't to my taste personally and never used in my working life so I have forgotten pretty much all of it. I suspect what you are after is possibly more advanced than what I did. I downloaded the PDF and unfortunately it triggered nothing from my vague recollections. I am really sorry - but it does seem something not widely known and experts in this don't seem to be common on this forum.

However a search on it did bring up a number of hits eg:
https://en.wikipedia.org/wiki/Bland's_rule
http://cs.brown.edu/courses/csci1490/notes/day9.pdf

They may be able to kelp you. If you find any issues in the second document that explains it, then since it starts from basic principles of the simplex algorithm, then me or someone may be able to help.

Thanks
Bill

 

[StoneTemplePython]

There's a few issues here.

First, this isn't a general Linear Programming issue but a specific Simplex Issue. I.e. this is a pivoting rule, not something that comes up in interior points.

In a nutshell: in optimization dealing with ties is tricky. When you are pivoting in Simplex, at each time you are choosing a basis you basically are greedy and choose the best one of the 'nearby' ones . If there is strict dominance (i.e. there is always a strictly best choice) then the process must stop after a finite number of iterations. If you have ties, you can get stuck in an infinite loop and Bland's rule is a way to prevent that from happening.

I have no clue what the non-defined "dictionaries" are in OP's post.

In addition, the exact mechanics of how and why Bland's rule prevents you from getting in an infinite loop is a very granular topic and requires a much more granular answer than I have. I have a hunch that there is someone in the math homework forums who knows the answer but he generally doesn't respond when people don't type up their problem and instead drop in images.

An alternative approach since this really is an algorithms question is to check stackoverflow.

 

[bhobba]

In addition, the exact mechanics of how and why Bland's rule prevents you from getting in an infinite loop is a very granular topic and requires a much more granular answer than I have.

The second document I posted explains why it works.

Thanks
Bill

 

[StoneTemplePython]

The second document I posted explains why it works.

Thanks
Bill

Isn't the custom to just flag it with a bold edit? From what I can tell you edited your post and added those links after I chimed in, but it's not particularly obvious.

 

[bhobba]

Isn't the custom to just flag it with a bold edit? From what I can tell you edited your post and added those links after I chimed in, but it's not particularly obvious.

My recollection is I had those links in from the start, but did edit some of my commentary.

I am unsure exactly what your concern is, just exactly what do you want me to make bold?

I gave it my like because its something I didn't even think of, but ensuring those reading the thread get a clear picture of exactly how the thread evolved is important.

Thanks
Bill

 

[mertcan]

first of all thanks for your return, but I still get stuck. I have tried to find different proofs and I would like to share one of them here https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss11/OPT/lec7.pdf . If you look at page 2 bland rule proof exists, but proof is made using contradiction method and I do not understand why contradiction exist ? or what is the contradiction? could you help me about that?

 

[fresh_42]

Without having checked the proof in detail, i.e. I simply watched for the contradiction, the author has shown that $\bar{c}^Td \gt 0$ in the first part and $\bar{c}^Td \lt 0$ in the last part, which cannot both be true.

 

[FactChecker]

At the beginning, it says xs is entering variable and when it enters objective value does not change( because all dictionaries are degenerate) which means xs will become basis and have 0 value.

I don't think that I agree with that. (Although I don't know what it means for the dictionaries to be degenerate.) The algorithm can cycle between feasible solutions with the same value of the objective function where two variables are being swapped in and out of the basis and have value 0 when they are out of the basis and non-zero value when they are in.

 

[fresh_42]

I don't think that I agree with that. (Although I don't know what it means for the dictionaries to be degenerate.) The algorithm can cycle between feasible solutions with the same value of the objective function where two variables are being swapped in and out of the basis and have value 0 when they are out of the basis and non-zero value when they are in.

But isn't the Bland rule what is expected to avoid this and theorem 1 assumes it to hold?

 

[FactChecker]

But isn't the Bland rule what is expected to avoid this and theorem 1 assumes it to hold?

Yes, Bland's rule avoids cycling. I was referring to statements @mertcan made in the first post. Maybe I don't understand something. The attachment does not include the statement of the theorem it is trying to prove, so I don't know what is assumed or stated. And for some reason small parts of the proof are blotted out of the attachment.

 

[fresh_42]

Yes, Bland's rule avoids cycling. I was referring to statements @mertcan made in the first post. Maybe I don't understand something. The attachment does not include the statement of the theorem it is trying to prove, so I don't know what is assumed or stated. And for some reason small parts of the proof are blotted out of the attachment.

Yeah, I directly went to the pdf, which was easier to understand. @mertcan's posts lack a bit of clarity and capital letters.

 

[mertcan]

Hi, initially please focus on what I shared my last attachment do NOT look the previous at post 1 :D. I believe this proof is more explanatory than previous one. My question is so simple by the way. Why the variable $$xs=q$$ can be everything??
I believe $$xs$$ only be zero because among degenerate iterations entering variable and leaving variable must be 0...

Also if you look at this link you can examine a similar proof of my attachment in the link http://profs.sci.univr.it/~rrizzi/classes/LP/homeworks/Bland/Bland.html. And there is sentence that "it must admit any solution which is admitted from

. In particular, it must be satisfied by the following choice of values": $$xs=y$$
Why must it admit any solution thus must the choice of values be $$xs=y$$ ??
Again I consider that it must be only 0 can not be any choice of value..