0
$\begingroup$

I am coding a Two-Phase Simplex solver, just as a part to improve my programming skills. I am testing this program on many LP problems, and I found one where it doesn't work as expected, so I want to know the optimal way to deal with this kind of situation in a LP problem. I did some research about it but couldn't find the right info. Hope to find it here

Suppose Phase I of Simplex is succesful (so the objective value in this phase is equal to zero), meaning that the sum of artificial variables is zero. This means a feasible solution for the original problem has been found, now we use Phase II to find the optimal solution of the original problem. Suppose that atleast one artificial variable remains in the basis after Phase I (with a value of 0), meaning that we may get an infeasible solution if any of the artificial variable is increased in Phase II. Of course, we don't want this, as we want an optimal solution for which all artificial variables that survived Phase I are kept to zero. My question is

(a) How to avoid (in the given case) getting an infeasible solution? What steps (algorithm or just logical steps) should be taken in order to avoid this?

(b) Is there a better way to manage this, e.g, is there any way to get rid of the artificial variables for the basis in Phase I?

The solution that I have in mind is the next, supposed the case explained before. For clarification, row 0 is the one with the objective function values (maximization problem).

1) Obtain a feasible solution (possibly non-optimal) in phase I, where some artificial variables didn't leave the basis.

2) Remove the columns in Simplex Tableau belonging to the non-basic variables after phase I.

3) Replace row 0 of Simplex Tableau for the correspoding objective function of the problem (the columns of artificial variables have a 0 on it).

4) Express the row 0 in terms of non-basic variables with row operations.

5) Find optimal solution using simplex method (until row 0 -except maybe the optimizing value- is non-negative). If all artificial variable are zero, then solve for the original problem variables. If not, go to 6.

6) If any artificial variable is non-zero try make any such variable leave the basis in exchange of some non-artificial variable, by using row operations.

7) Iterate steps 5 and 6. But now the stopping condition is different: stop when all artificial variables are equal to 0 and all the values of row 0 (except maybe the objective value and the values belonging to the artificial variables) are non-negative.

Let me know if you need more info to be able to help, e.g., I can provide the example that wasn't working for me.

$\endgroup$
0
$\begingroup$

If the row of the tableau corresponding to this basic artificial variable $a$ has a nonzero entry for any column corresponding to a non-artificial variable $x$, you can do a pivot on that entry: $a$ leaves the basis as desired, and $x$ enters with value $0$; since the value of the artificial variable was $0$, this is a degenerate pivot that does not change the value of any variables, so it does not affect feasibility. You can then delete the column for this artificial variable, and continue as usual.

On the other hand, if there are no such nonzero entries, the equation corresponding to this row says that the artificial variable is automatically $0$. Then you may safely delete this row from the tableau. Even if you leave it in, there is no danger of it ever getting a nonzero value: no future pivots will change it at all.

$\endgroup$
  • $\begingroup$ I like this solution because I don't need to modify my solver function! Just what I was looking for, thank you! $\endgroup$ – user57284 Jun 7 at 19:05

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.