Simplex Strategy

Question

I would like to know if there is a strategy to wisely choose the pivoting variables only by observing the limits given for "y" (lower and upper bound)?

For example, given a random matrix and its limits such as:
-oo <= x0 <=  +oo
-oo <= x1 <=  +oo
-oo <= y0 <= 1
-1 <= y1 <= +oo
3 <= y2 <= +oo

Should I start pivoting y1 because it has the lowest lower bound or should I start with y0 because it has the lowest upper bound limit? Or anything else?
Because by using such strategy (or anything else) I believe the simplex could be solved precisely in few steps.

Comments

Without knowing the coefficient of a variable, you can't tell which direction to move its value to, and hence whether you the upper or the lower bound is relevant.

---

Not really an answer to your question, but if you are looking for a strategy to avoid the exponential worst case running time of the simplex algorithm, you might want to look at the Interior-point method as an alternative, which has polynomial complexity.

Answer 1

Your questions makes a lot of sense, and was and is still a topic of research. A couple of heuristics for the Simplex method were suggested, but none of them (as being heuristics only) could guarantee a quick solution. So, there is no clear answer to your question, I am afraid.

Answer 2

As stated in the other answer there is currently no way to determine suitable answers by only observing the limits.

Lets consider both rules you were shown in the lecture slides 64/107 and 76/107:

The first one checks for suitable variables, since we need to make sure that there is some "space" in which we can "move" our variable. Basicly our formula takes two things into account, first if our variable which harms its constraint is greater than the upper bownd (to large) or smaller than the lower bound (to small), and second it checks if the variable we want to swap with has some space in the corresponding direction. Therefore we need to consider the factor with which both variables relate. If our first variable is for example to large and our variable we want to swap with, is at its upper bound, then we are allowed to swap, if the factor which relates both variables is positive. This is because we could make the second variable smaller and as a result the first variable would also get smaller. If however the factor is negativ we are not allowed to swap, since we can not manipulate the second variable in a way that the first one will stay inside its bounds.

As can be seen here the factors which relate the bound and the unbound variables are important to find out pivoting partners and it is therefor not sufficient to only observe the bounds. If all the factors would be negative for example, each heuristic would need to be flipped.

Lets consider the second rule on page 76/107 (Blands rule):

To enforce termination we fix a variable ordering and always swap according to the variable ordering. It should be noted that usually we have (x_0 > x_1 > y_0 > y_1 > y_2), while we start with x_0 then x_1, followed by y_0 and so on. While it might be possible to find a more efficient method of determining potential pivoting partners, this might not lead to termination of the whole procedure.

To recap: As stated there is currently no way of "smartly" choosing variables, since this leads to a different set of problems, while at best this would be a heursitic, since the sign of the corresponging factor is important. In addition to that, for the exam you have to do the simplex algorithm as stated in the slides, which means you have to use the rules for finding pivoting partners stated on slide 64/107 and 76/107