stalling

16:24 Nov 16, 2014 

Cycling can be eliminated e.g. by http://en.wikipedia.org/wiki/Bland's_rule

Stalling is less serious in that progress is eventually made but, as far as I know, can't be eliminated.

You'd really need a printed book to decide :-)

Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8.
Акулич И.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9.
Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4.
В. Н. Шевченко, Н. Ю. Золотых Линейное и целочисленное линейное программирование. — Нижний Новгород: Издательство Нижегородского госуниверситета им. Н.И. Лобачевского, 2004. — С. 63-66 (раздел 2.8. Замечания о сложности решения ЗЛП).

16:15 Nov 16, 2014 

Really, it must be less serious, stalling stays at the same basic solution although changing bases for several iterations, before moving to the next solution. I wanted запаздывание. Вырожденные итерации sounds even more exact, if I understand everything correctly. But google doesn't confirm anything in Russian, it finds only зацикливание. Should I follow the rules or be brave?
Some more context: All we know is that one of these dictionaries, one of the 20, or at least one of the 20, is final. So, therefore, what simplex is going to do is, in one step, it's going to achieve the optimal solution, but it doesn't know about it. So, it can stall in the worst case for up to 20 steps. Go through each and every one of these dictionaries here, before you get to a final dictionary, and stop. And, that can happen, okay? And, polyhedra where these can happen are highly degenerate polyhedra. And, they can be constructed, they're not hard to construct. And, you can make the *stalling problem* for simplex really bad. In general it's very hard to predict.