1
$\begingroup$

I'm coding the simplex method and observing that it easily falls into cycling, even if Bland's rule is used. It seems to me I have found the reason and I would like to check my understanding is correct.

It seems the problem is in tiny detail of the choice of the pivot row.

We choose the pivot row "r" by the codition

B_r / A_{rc} is minimal over "r" among all NONnegative values B_r / A_{rc}

It seems to me the correct way is to change from NONnegative to strictly positive. Is it correct ?

At least it helps in my example and seems Okay from theory point of view (well, I am not sure I completely understand the theory).

(In textbooks like Hamdy A. Taha and all internet pages they say about "NONnegativity" )


Here is example of cycling with Bland's rule:

simplexMatrix =

1.0e+04 *

-1.0999 -0.9000 -0.7000 0 0 0 0 0 -0.9000 0.0001 0.0001 0.0001 0.0001 0 0 0 0 0.0001 0.0010 0.0008 0.0006 0 0.0001 0 0 0 0.0008 0.0001 0 0 0 0 0.0001 0 0 0.0001 0 0.0001 0 0 0 0 0.0001 0 0.0001 0 0 0.0001 0 0 0 0 0.0001 0.0000

simplexMatrix =

1.0e+03 *

     0   -0.2008   -0.4006         0    1.0999         0         0         0   -0.2008
     0    0.0002    0.0004    0.0010   -0.0001         0         0         0    0.0002
0.0010    0.0008    0.0006         0    0.0001         0         0         0    0.0008
     0   -0.0008   -0.0006         0   -0.0001    0.0010         0         0         0
     0    0.0010         0         0         0         0    0.0010         0    0.0006
     0         0    0.0010         0         0         0         0    0.0010    0.0004

simplexMatrix =

1.0e+03 *

     0         0   -0.2500         0    1.1250   -0.2510         0         0   -0.2008
     0         0    0.0003    0.0010   -0.0001    0.0002         0         0    0.0002
0.0010         0         0         0         0    0.0010         0         0    0.0008
     0    0.0010    0.0007         0    0.0001   -0.0013         0         0         0
     0         0   -0.0007         0   -0.0001    0.0013    0.0010         0    0.0006
     0         0    0.0010         0         0         0         0    0.0010    0.0004

simplexMatrix =

1.0e+03 *

     0    0.3333         0         0    1.1667   -0.6677         0         0   -0.2008
     0   -0.0003         0    0.0010   -0.0002    0.0007         0         0    0.0002
0.0010         0         0         0         0    0.0010         0         0    0.0008
     0    0.0013    0.0010         0    0.0002   -0.0017         0         0         0
     0    0.0010         0         0         0         0    0.0010         0    0.0006
     0   -0.0013         0         0   -0.0002    0.0017         0    0.0010    0.0004

simplexMatrix =

1.0e+03 *

     0   -0.2008   -0.4006         0    1.0999         0         0         0   -0.2008
     0    0.0002    0.0004    0.0010   -0.0001         0         0         0    0.0002
0.0010    0.0008    0.0006         0    0.0001         0         0         0    0.0008
     0   -0.0008   -0.0006         0   -0.0001    0.0010         0         0         0
     0    0.0010         0         0         0         0    0.0010         0    0.0006
     0         0    0.0010         0         0         0         0    0.0010    0.0004

Here is the same without Bland's rule

simplexMatrix =

1.0e+04 *

-1.0999 -0.9000 -0.7000 0 0 0 0 0 -0.9000 0.0001 0.0001 0.0001 0.0001 0 0 0 0 0.0001 0.0010 0.0008 0.0006 0 0.0001 0 0 0 0.0008 0.0001 0 0 0 0 0.0001 0 0 0.0001 0 0.0001 0 0 0 0 0.0001 0 0.0001 0 0 0.0001 0 0 0 0 0.0001 0.0000

simplexMatrix =

1.0e+03 *

     0   -0.2008   -0.4006         0    1.0999         0         0         0   -0.2008
     0    0.0002    0.0004    0.0010   -0.0001         0         0         0    0.0002
0.0010    0.0008    0.0006         0    0.0001         0         0         0    0.0008
     0   -0.0008   -0.0006         0   -0.0001    0.0010         0         0         0
     0    0.0010         0         0         0         0    0.0010         0    0.0006
     0         0    0.0010         0         0         0         0    0.0010    0.0004

simplexMatrix =

1.0e+03 *

     0    0.3333         0         0    1.1667   -0.6677         0         0   -0.2008
     0   -0.0003         0    0.0010   -0.0002    0.0007         0         0    0.0002
0.0010         0         0         0         0    0.0010         0         0    0.0008
     0    0.0013    0.0010         0    0.0002   -0.0017         0         0         0
     0    0.0010         0         0         0         0    0.0010         0    0.0006
     0   -0.0013         0         0   -0.0002    0.0017         0    0.0010    0.0004

simplexMatrix =

1.0e+03 *

     0   -0.2008   -0.4006         0    1.0999         0         0         0   -0.2008
     0    0.0002    0.0004    0.0010   -0.0001         0         0         0    0.0002
0.0010    0.0008    0.0006         0    0.0001         0         0         0    0.0008
     0   -0.0008   -0.0006         0   -0.0001    0.0010         0         0         0
     0    0.0010         0         0         0         0    0.0010         0    0.0006
     0         0    0.0010         0         0         0         0    0.0010    0.0004
$\endgroup$
1

1 Answer 1

4
$\begingroup$

The short answer to your question is that "nonnegative" is correct. 0 ratios do occur and it is sometimes necessary to perform degenerate pivots in order to ultimately reach a solution which will pass the simplex method's optimality test. However, you need to carefully deal with near zero values of $B_{r}$ and $A_{rc}$ or else round-off can easily lead to incorrect pivot selections.

Notation for the simplex method in tableau form is not completely standardized. In the following, I'll assume that we're solving a maximization problem, so that variables with positive reduced costs are candidates to enter the basis. You can easily adjust this for minimization problems.

In practice, because of floating point round off errors, it can be difficult to determine whether $B_{r}$ is 0, positive, or negative (which would be an error condition.) You'll need to set a tolerance $\epsilon$, and declare $B_{r}$ to be effectively 0 if $| B_{r} | \leq \epsilon$. If $B_{r} > \epsilon$, then $B_{r}$ is effectively positive. Similarly, if $B_{r} < -\epsilon$, then $B_{r}$ is effectively negative and you should stop with an error.

Furthermore, you need to check whether $A_{rc}$ is effectively zero ($|A_{rc} \leq \epsilon$) or whether it is effectively positive. The basic variable in row $r$ is a candidate to leave the basis only if $A_{rc}$ is effectively positive. Do not consider row $r$ if $A_{rc}$ is effectively 0 or negative.

In computing the ratio $B_{r}/A_{rc}$ where $A_{rc}$ is effectively positive and $B_{r}$ is effectively 0 you should replace the actual value of $B_{r}$ by 0 and treat the ratio as 0. For example, suppose $\epsilon=1.0e-8$. If $A_{rc}=10$ and $B_{r}=-1.0e-16$, then you should treat the ratio as 0. Similarly, if $A_{rc}=10$ and $B_{r}=+1.0e-16$, then you should treat the ratio as 0. If you do not do this, then round off errors can easily lead you to incorrectly conclude that the ratio for some row is negative when it's really effectively 0.

Now, Bland's rule can be stated as follows.

  1. Consider only columns where the reduced cost is effectively positive. Let $c$ be the first column with an effectively positive reduced cost. (I'm assuming here that the columns are kept in the original order of the variables- you want the entering variable $x_{j}$ with the smallest $j$.)

  2. Consider only rows $r$ where $A_{rc}$ is effectively positive.

  3. For those rows under consideration, compute the ratios $B_{r}/A_{rc}$, replacing effectively 0 values of $B_{r}$ with actual values of $0$.

  4. Pick $r$ corresponding to the smallest ratio if there is a unique row with this ratio. If there are multiple rows with the same minimum ratio then pick the one with the smallest index $r$. (I'm assuming here that you've ordered the rows by the indices of the basic variables- you actually want to pick the leaving basic variable with the smallest index among those that are tied.)

$\endgroup$
1
  • $\begingroup$ Thank you very very very much for your answer ! Condition 2 "Consider only rows rr where Arc is effectively positive." I was somehow missing this condition and simplex method worked any way (I passed millions test on random data). May I ask you to comments on this condition - what is is sense, what is its nature ? In textbook like Hamdy A. Taha it seems this condition is not mentioned, as well as in many inet sources. Also it is not clear for me from theory point of view - it seems that if RATIO b/A >= 0 it is enough to ensure that Xi would be nonnegative - so why do we need A_rc > 0 ? $\endgroup$ Commented Feb 1, 2016 at 12:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.