HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Mistake in a proof of termination phase of Simplex algorithm in CLRS?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
phaseclrsmistakealgorithmsimplexterminationproof

Problem

There is a pseudo-code for Simplex algorithm in CLRS:

The proof consists from three-part loop invariant:

Proof We use the following three-part loop invariant:

At the start of each iteration of the while loop of lines 3–12,

  • the slack form is equivalent to the slack form returned by the call of INITIALIZE-SIMPLEX,



  • foreach $i \in B$, we have $b_i$ >= 0, and



  • the basic solution associated with the slack form is feasible.



The initialisation and maintenance phases are clear for me.
But, the termination case seems(not sure) wrong to me:

So, my question is:

It is unclear for me that $\bar{x_i} = \infty $ if $i = e$. But, if we look at the pseudo-code, it is obvious that such thing happens only if $x_e \leq 0$. What am I missing ?

Solution

Because of line 9, $\Delta_l$ is going to be $\infty$ if and only if all the $\Delta_i$ with $i \in B$ are $\infty$. This can happen only when all the $a_{ie}$ with $i \in B$ are $ \le 0$. Hence, by construction the solution $\bar{x}$ satisfies $\bar{x}_i \ge 0$ for all $i$. Therefore it is both feasible and it has unbounded objective value.

If you are confused by the $\infty$, as Marcus Ritt mentioned in a comment you can replace the $\infty$ in the definition of $\bar{x}$ with a very large value $M$ and consider what happens as $M$ tends to $\infty$.

Context

StackExchange Computer Science Q#110991, answer score: 3

Revisions (0)

No revisions yet.