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.