I'm facing a problem programming a full tableau solver for some LP problems.
The difficulty is when the test for leaving (line) variable cannot find a single positive value on the pivot column for the Minimum Ratio Test.
When this happens, the program backtracks and tries another entering (column) variable candidate. But there's a dead-end eventually.
For the choice of entering column I've tried two methods:
- Fast rate of increase of object function
- Smallest subscript (lowest column index)
My question is, when this happens is the problem impossible to solve or I'm making a big mistake? I've run the same problem on lp_solve and it runs just fine.
Thanks.
Best Answer
When you can't find a single positive value in the pivot column it means that the linear program is unbounded. In other words, you can increase the objective function indefinitely while maintaining a feasible solution. So, if this happens, your algorithm shouldn't backtrack and try to find another candidate for the entering variable; it should tell the program to stop and declare that the problem is unbounded. If you are getting this situation on a problem you know is bounded then there is a bug somewhere else in your code.
Let's look at an example to see why no positive values in the pivot column means the LP is unbounded.
$$ \begin{matrix} \text{Basic Variable}& Z & x_1 & x_2 & x_3 & x_4 & x_5 & \text{Right-Hand Side}\\ \hline Z & 1 & 1/2 & -2 & 0 & 3/2 & 0 & 3 \\ \hline x_3 & 0 & 1/2 & 0 & 1 & 1/2 & 0 & 1 \\ x_5 & 0& -1 & -1 & 0 & -1 & 1 & 0 \\ \end{matrix} $$
In this example, the only choice for leaving variable is $x_2$, and there are no positive values in its pivot column. If we rewrite the tableau in equation form, it becomes $$Z = 3 - 1/2x_1 + 2x_2 - 3/2 x_3,$$ $$x_3 = 1 - 1/2x_1 - 1/2 x_4,$$ $$x_5 = 0 + x_1 + x_2 + x_4.$$
Letting $x_2$ enter the basis means increasing $x_2$. Normally, we increase the entering variable until doing so any more would make one of the current basic variables negative (and thus the current solution infeasible). However, the fact that there are no positive values in $x_2$'s column means that increasing $x_2$ does not cause any of the current basic variables to decrease: the value of $x_3$ remains at $1$, the value of $x_5$ actually increases with $x_2$, and the values of $x_1$ and $x_4$ remain $0$. Thus we can increase $x_2$ indefinitely without any other variable going negative, which means we can increase the objective function indefinitely in this direction without the current solution ever becoming infeasible. This means the problem is unbounded.