Originally posted by: Aaron.Sun

I am working on a problem about the extreme point of linear program. The problem is highly degenerate. 

I tried to observe the intermediate iterations when use primal simplex to solve the problem. I expected that every intermediate iteration means a feasible solution at the extreme point of the polyhedron. But it seems the algorithm is not searching by moving from one extreme point to another. (But I am not sure, so need get confirmation from this forum.)

After I turn off the perturbation (using primal simplex), it seems Cplex still modified the original problem somewhat. At the end of iterations, it display: Removing shift (see the pic below). What does that mean? Is the solution at each iteration a feasible solution of the original problem? Area all iterations at extreme points?

Thank you!

Originally posted by: Aaron.Sun

do not know why the image does show up.

Here is the pic link: https://www.dropbox.com/s/450bfdyuuk33i3z/pic-CplexForum.PNG

Thank you!

Originally posted by: RWunderling

(In the case of primal Simplex): When CPLEX detects a longer sequence of degenerate pivots, i.e. pivots in which the primal solution vector does not move but is only represented by a different basis, it perturbs the rhs and bounds of the problem slightly as to artificially remove the perturbation and being able to find pivots that move the primal solution vector.  These solution vectors are no longer neccessarily feasible for the unperturbed problem.  Thus, when the perturbed problem has been solved, CPLEX undoes the perturbation and verifies if the resulting solution vector is feasible for the original problem as well.  If not it proceeds with the algorithm.
Thus, there is no guarantee that, even in phase 2, the current primal simplex solution is indeed primal feasible at any time.  Such guraantee is only provided for the final solution (up to tolerances).

Roland

Originally posted by: Aaron.Sun

Thank you.

One more question: If use primal simplex, is there a guarantee that the final solution is an extreme point in the case that multiple optimal solution exist?

Originally posted by: RWunderling

Yes, the primal Simplex algorithm will converge to a vertex (up to tolerances) of the underlying polyhedron.

Originally posted by: T_O

Remember that not everything is a vertex, e.g.

min x+y
s.t. x+y = 2
x,y unbounded

obviously has an optimal value, but no vertex in 2 dimensional space.

Best regards,
Thomas