3
$\begingroup$

I've been running into an issue choosing a pivot when there are constraints with an RHS of zero. It appears that sometimes you should include zero test ratios when searching for the minimum test ratio, and sometimes you shouldn't. What is the hard and fast rule to handle zero test ratios?

For a simple demo, say you want to maximize $y$ subject to $x + y \le 1$ and $y \le x$. An x/y graph of the solution space shows a triangle with the top at $x = \frac{1}{2}, y = \frac{1}{2}$. To maximize $y$ we should end up at this point.

The first table: $$0: \begin{bmatrix} & x & y & s_1 & s_2 & = \\ s_1 & 1 & 1 & 1 & 0 & 1 \\ s_2 & -1 & 1 & 0 & 1 & 0 \\ & 0 & -1 & 0 & 0 & 0 \end{bmatrix} $$

The only possible entering variable is $y$ with a negative cost of -1. Then to select the pivot row, we find the two ratios. Row 1 $1 / 1 = 1$, row 2 $0 / 1 = 0$. Here is the problem. As I understood, in order to choose a pivot row, the ratio test must be positive. If we follow that rule, it leaves only one option of leaving variable, $s_1$. So let's try following the rule: $$1: \begin{bmatrix} & x & y & s_1 & s_2 & = \\ y & 1 & 1 & 1 & 0 & 1 \\ s_2 & -2 & 0 & -1 & 1 & -1 \\ & 1 & 0 & 1 & 0 & 1 \end{bmatrix} $$

This breaks another rule: $s_2$ shouldn't be negative, right? Second, there is no negative in the objective row, so we're done. But we're at $x = 0, y = 1$ which isn't even a solution, because $s_2$ is an illegal value. Let's try picking row 2 instead, the one with the test ratio of 0: $$1': \begin{bmatrix} & x & y & s_1 & s_2 & = \\ s_1 & 2 & 0 & 1 & -1 & 1 \\ y & -1 & 1 & 0 & 1 & 0 \\ & -1 & 0 & 0 & 1 & 0 \end{bmatrix} $$

Now $x$ must enter. We are supposed to only pivot on positive test ratios. We didn't follow that rule last time, but we'll arbitrarily follow it now and have $s_1$ leave: $$2: \begin{bmatrix} & x & y & s_1 & s_2 & = \\ x & 1 & 0 & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ y & 0 & 1 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ & 0 & 0 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \end{bmatrix} $$

And this is the answer. Out of curiosity, since we arbitrarily broke the 'positive' rule for pivot $1'$ and arbitrarily followed it for pivot $2$, let's try being consistent and always including zero when searching for the minimum test ratio. That means for pivot $2$ we should have chosen $y$ as the leaving variable since its test ratio ($0 / -1 = 0$) is smaller than the top row's ($1 / 2 = \frac{1}{2}$). $$2': \begin{bmatrix} & x & y & s_1 & s_2 & = \\ s_1 & 0 & 2 & 1 & 1 & 1 \\ x & 1 & -1 & 0 & -1 & 0 \\ & 0 & -1 & 0 & 0 & 0 \end{bmatrix} $$

Row 2 is always going to have a zero test ratio, apparently. So if we're going to consistently include zeros, we have to choose it again. $y$ enters, $x$ leaves. $$3: \begin{bmatrix} & x & y & s_1 & s_2 & = \\ s_1 & 2 & 0 & 1 & -1 & 1 \\ y & -1 & 1 & 0 & 1 & 0 \\ & -1 & 0 & 0 & 1 & 0 \end{bmatrix} $$ Which is identical to pivot $1'$, and we will cycle without arriving at a minimum.

To recap: how does one know exactly when and when not to include zeros when searching for the minimum test ratio, since excluding all zeros leads to invalid pivots and including all zeros leads to cycling? Or did I somehow start with a matrix that isn't in standard form?

$\endgroup$
1
$\begingroup$

Indebted to zifyoip for clearing up a fundamental misunderstanding for me:

The rule is not that the test ratio must be positive, but that the pivot entry must be positive. You can't pivot on a nonpositive entry of the tableau.

There are several ways to prevent cycling. One is to break ties in the test ratios randomly—this will eventually (almost surely) break cycles. Another is to randomly perturb the entries of the initial tableau slightly (add or subtract small random quantities from all of them), or to add symbolic powers of ε to the entries (ε acts as an infinitesimal: ε > 0, but ε < x for all positive real numbers x; and ε ≫ ε2 ≫ ε3 ≫ ...; this requires some symbolic manipulation to keep track of powers of ε through the pivots). There are also deterministic rules for avoiding cycling, such as Bland's rule.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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