1
1

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 14 Mar '11, 07:56

Ram's gravatar image

Ram
51941029
accept rate: 0%

2

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

(14 Mar '11, 08:25) Bo Jensen ♦
1

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.

(14 Mar '11, 19:43) Venky
1

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.

(08 May '11, 01:34) Ram

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

(12 May '11, 16:09) Samik R.

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.

link

answered 10 May '11, 04:37

Erling's gravatar image

Erling
4404
accept rate: 0%

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.

link

answered 11 May '11, 16:04

Philipp%20Christophel's gravatar image

Philipp Chri...
1.0k27
accept rate: 22%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×37
×29
×24

Asked: 14 Mar '11, 07:56

Seen: 10,363 times

Last updated: 12 May '11, 16:09

OR-Exchange! Your site for questions, answers, and announcements about operations research.