0

The necessary condition is found to be degeneracy at the presence of more than one leaving variable is essential for multiple optimal solutions. But what is the sufficient condition?

Is $C-C_b*inv(B)*A=0$ is sufficient one?

Also if one has one optimal solution along with the in formation about basic and nonbasic elements, is there any method to obtain all optimal solutions (the vertex solutions).

Parikshit
  • 102
  • I don't think there exist a simple condition you can use to check for the (proven) existence of multiple solutions. Note that multiple bases can actually indicate the same primal solution. Enumerating all solutions is not easy either. It is possible to enumerate all optimal bases by encoding the basis using binary variables (see here). – Erwin Kalvelagen Aug 11 '17 at 19:09
  • @ErwinKalvelagen I am able to produce some solutions out of many by using single step of revised simplex method. Here, the incoming variable is the non-basic one with reduced cost coefficient equals to zero. Though there are many possibilities of (sequence of entering the nonbasic variables etc.). So, what about using this paper given in the link or many others:

    http://www-personal.umich.edu/~murty/segments.pdf

     – Parikshit Aug 13 '17 at 13:23
  • Why not. Katta Murty is a reputable researcher. Note that the paper has a caveat about guaranteeing to find all optima. – Erwin Kalvelagen Aug 14 '17 at 02:42

0 Answers0