# Variable leaving basis in linear programming - when does it happen?

In the simplex algorithm in linear programming,

what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)?

I'm supposed to list as many sufficient and necessary conditions as possible for some basic variable $x_q$ which could be slack, artificial or non-slack and non-artificial.

Let $x_q$ be the s-th basic variable. Suppose the s-th row of some current simplex tableau has 1 in the column of $x_q$ and 0's everywhere else. Under what circumstances, if any, might $x_q$ leave the basis? Can any of the values in the s-th row of the tableau ever change?

Well since it's a basic variable, I'm guessing the $x_q$ column already has 0's everywhere except in the s-th row. Now, the $x_q$ row has 0's everywhere in the column of $x_q$ like: This is in the context of the Big M Method and artificial variables. I'm not quite sure what the relationship is exactly, though.

Edit: It looks like one of the constraints is the original (maximisation?) problem has something like

$$x_2 = 10$$

or

$$x_4 = 0$$

I guess the relationship would be Big M Method applies for equality constraint?

But I think an equality constraint like for example

$$x_4 = 0$$

$$x_4 + x_5 = 0$$

with $z$ being replaced with $z' = z - Mx_5$

So

$$x_4 + x_5 = 0$$

doesn't exactly lead to a row of all but one zero entry? There are two non-zero entries?

What I tried:

$x_q$ leaves if there is some non-basic variable $x_r$ that enters because

1. $$z_r - c_r < 0$$

2. $$z_r - c_r = \min_j (z_j - c_j)$$

3. $$\frac{b_q'}{a_{qr}'} = \min_i \{\frac{b_i'}{a_{ir}'} | a_{ir}' > 0 \}$$

Is that right? Any other sufficient or necessary conditions?

What is the relevance of the 0's in the row?

Edit:

I guess an example would be something like

\begin{bmatrix} 2 & 0 & 10\\ 0 & 1 & 0\\ 5 & 0 & 6 \end{bmatrix}

If $x_q$ leaves and then $x_r$ enters where $x_q$'s column is the second column, and then $x_r$ is, say, the first column. What would be the EROs?

$$\color{red}{\frac{1}{2}R_1 + R_2 \to R_2}$$ $$-2R_2 + R_1 \to R_1$$ $$-5R_2 + R_3 \to R_3$$

I have never had to make $\color{red}{\text{a zero entry to a non-zero number}}$ in the simplex method.

I find this suspicious. Should I not?

Perhaps the elements in the row can never change because $x_q$ can never leave?

Or $x_q$ can never leave because row can never change?

• If there is a non basic variable $x_r$ such that $z_r-c_r=0$ (and all others are $< 0$) and point 3 (the one about the min ratio) is satsified one can still force $x_q$ to leave and $x_r$ to enter. This will not improve the optimal value but give an alternative solution.
– user10575
May 7, 2016 at 10:55
• I am not clear why you are insisting that the $q$th row will have all but one entries $0$.
– user10575
May 7, 2016 at 10:56
• @Shahab 1 thanks! ^-^ post as answer? 2 re 'I am not clear why you are insisting that the $q$th row will have all but one entries $0$.' --> 'Suppose the s-th row of some current simplex tableau has 1 in the column of $x_q$ and 0's everywhere else.' ? I mean that's in the problem. You mean you don't think it's relevant?
– BCLC
May 7, 2016 at 11:15
• @Shahab Did you mean 'and all others are $\color{red}{\ge}0$'? Or $<0$ but for $c_r - z_r$ rather than $z_r - c_r$?
– BCLC
May 7, 2016 at 11:40
• Yes I meant all other $z_r-c_r\ge 0$ (assuming the problem is a max problem), And yes, I see no reason why the $q$th row should be what you say.
– user10575
May 7, 2016 at 16:32

# 1. Lets show $x_q$ can't leave the basis

## Intuitively

If the row $s$ contains all zeros except in the column of $x_q$, it means the problem contains a constraint of the type

$$x_q = b_s$$

In that case, only solutions with $x_q = b_s$ are feasible, so the variable $x_q$ never leaves the basis.

## Mathematically

$x_q$ leaves if there is some non-basic variable $x_r$ that enters because

1. $$z_r - c_r < 0$$

2. $$z_r - c_r = \min_j (z_j - c_j)$$

3. $$\frac{b_q'}{a_{qr}'} = \min_i \{\frac{b_i'}{a_{ir}'} | a_{ir}' > 0 \}$$

It is true, assuming the problem is about maximization.

Now, lets apply this to the case where the row corresponding to $x_q$ contains only zeros except in the column corresponding to $x_q$. You have $$z_q = 1\times c_q = c_q$$

So $z_q- c_q = 0$, which is normal since $x_q$ is a basic variable.

Now, let $x_r$ be the entering variable. From the asumptions of the problem, we know that $a'_{qr} = 0$. This implies

$$\min_i \{\frac{b_i'}{a_{ir}'} | a_{ir}' > 0 \} \neq \frac{b_q'}{a_{qr}'}$$

This means the variable $x_q$ never leaves the basis.

# 2. Let's show row $s$ can't change

## Intuitively

Lets call $x_r$ the entering variable, and $x_t$ the exiting variable.

Now lets see how the pivot will affect the column of $x_q$. We have

Line $i$ of the new tableau is a linear combinaison of lines $i$ and $t$ of the old tableau. Since these value are 0 for the column of $x_q$, the column of $x_q$ will never change. The reduced cost of variable $x_q$ will always be 0 and $x_q$ will never leave the basis.

## Mathematically

Lets call $x_r$ the entering variable, and $x_t$ the exiting variable.

When making the pivot for row $s$, the formulae is (assuming $a'_{ij}$ is the new value in the tableau and $a_{ij}$ is the old value.

$$a'_{si} = a_{si} - \frac{a_{qr}}{a_{tr}} a_{ti}$$

Since $a_{qr} = 0$, the row $s$ stays unchanged.

• Thanks a million fredq! ^-^ Any idea how this is related to the Big M Method? Or artificial variables?
– BCLC
May 18, 2016 at 18:00
• no idea. As I said, the situation described corresponds to a constraint $x_q = b_s$ so the variable can be removed from the problem. It may help if you provide more details on the context. Why do you think big M and artificial variables are important? May 18, 2016 at 18:19
• Hey actually I just realised. Big M Method can be used when an LP problem has an equality constraint and no slack variables right? The problem is from chapter 2 here
– BCLC
May 20, 2016 at 19:10
• Wait you said column of $x_q$. You mean row of $x_q$? I mean if $x_q$ never leaves the basis then the column of $x_q$ of course never changes?
– BCLC
May 20, 2016 at 19:11

If there is a non basic variable $x_r$ such that $z_r−c_r=0$ (and all others are $\ge 0$) and point 3 (the one about the min ratio) is satisfied one can still force $x_q$ to leave and $x_r$ to enter. This will not improve the optimal value but give an alternative solution

• Thanks Shahab. ^-^ This doesn't answer everything, but I guess it's better than nothing
– BCLC
May 7, 2016 at 16:43
• I edited my post...
– BCLC
May 13, 2016 at 16:43
• @BCLC: It would be good if you tell the detailed source of these questions.
– user10575
May 14, 2016 at 1:29
– BCLC
May 18, 2016 at 18:10

Assume we are dealing with a minimization problem. Any variable $x_r$ with negative ($\le 0$) reduced cost can enter the basis. Once this is done, another variable has to leave the basis. You can choose any variable $x_i$ such that $$\frac{b_i'}{a_{ir}'} \ge 0,$$ i.e. any variable such that if $x_r$ replaces $x_i$, the solution remains feasible. Typically we choose the variable that minimizes $\frac{b_i'}{a_{ir}'}|a_{ir}'>0$, because it gives you the best possible value for the entering variable, before the solution becomes infeasible.

So in this particular case, $x_q$ will leave the basis if and only if

1. There is another variable with a negative reduced cost (or positive if we are maximizing)
2. $\min_i\{\frac{b_i'}{a_{ir}'}|a_{ir}'>0\}=\frac{b_q}{a_{qr}'}=b_q$
• Oh thanks Kuifje. Wasnt notified. You mean maximisation? You mean nonpositive reduced cost?
– BCLC
May 11, 2016 at 22:57
• I edited my post...
– BCLC
May 13, 2016 at 16:43