while connecting LP concepts with real life situations, I stumbled on following questions, a) are there any practical problems, which can be categorized under Cyclic Type LP? b) and can there be any solution to such problems? Thanks in advance
asked
Ram |

After the invention of simplex method people discussed whether the simplex could cycle. After some time a few examples were found that proved that the simplex method could indeed cycle. It is very rare that simplex method cycles in practice because rounding errors, the occasionally refactorization sort of introduce a random perturbations that will break cycles. For further details consult for instance: Gill, P., W. Murray, M. Saunders, and M. Wright, "A Practical Anti-Cycling Procedure for Linearly Constrained Optimization," Mathematical Programming, 45, pp. 437-474, 1989.
answered
Erling |

If you talk about cycling in the theoretical sense, Erling's answer is probably what you are looking for. There is also something called "numerical" cycling or stalling. For this phenomenon this might help: a) It happens on many practial instances, especially combinatorial and mixed integer relaxations. It can also happen on some of the netlib instances. b) All modern LP solvers use a number of anti-degeneracy techniques to avoid this kind of cycling. The book by Maros "Computational Techniques of the Simplex Method" mentions a few. A little bit more up to date is Chapter 13 in "The Travelling Salesman Problem" by Applegate et al.
answered
Philipp Chri... |

Not sure what you mean by "Cyclic", perhaps you are referring to cycling when using the simplex method ?

I tried searching, if there was any term used in literature called "cyclic type" LPs, but couldnt find any. Pls do elaborate what you meant.

sorry for the delay.....was on long trip....yes it is in connection with simplex method....by cyclic condition, i mean when the same simplex iteration is repeated endlessly without improving the solution...just wonder how this concept came into existence without a practical case......thanks.

Interesting question - the answers so far include valuable literature pointers.