Glossary entry (derived from question below)
English term or phrase:
stalling
Russian translation:
вырожденные итерации (приводящие к запаздыванию результатов при выполнении симплекс-метода ).
English term
stalling
And, *stalling* occurs because in higher dimensions it's much more common to encounter this kind of
degeneracy where multiple faces, more than n faces meet at the vertex and give rise to a large number of dictionaries. Hopefully this is all clear and if so, we'll talk about Unbounded Polyhedra and Rays.
| 3 | вырожденных итераций |
DLyons
|
| 4 | замедление |
Nik-On/Off
|
Nov 18, 2014 14:00: *Alena* changed "Edited KOG entry" from "<a href="/profile/1200982">*Alena*'s</a> old entry - "stalling"" to ""вырожденные итерации (при выполнении симплекс-метода, приводят к запаздыванию результатов.)""
Nov 18, 2014 14:00: *Alena* changed "Edited KOG entry" from "<a href="/profile/1200982">*Alena*'s</a> old entry - "stalling"" to ""вырожденные итерации (при выполнении симплекс-метода приводят к запаздыванию результатов.)""
Nov 18, 2014 14:04: *Alena* changed "Edited KOG entry" from "<a href="/profile/1200982">*Alena*'s</a> old entry - "stalling"" to ""вырожденные итерации (при выполнении симплекс-метода приводят к запаздыванию результатов).""
Proposed translations
вырожденных итераций
--------------------------------------------------
Note added at 42 mins (2014-11-15 17:08:41 GMT)
--------------------------------------------------
Or почти вырожденными
--------------------------------------------------
Note added at 19 hrs (2014-11-16 11:58:20 GMT)
--------------------------------------------------
I'm not sure that the Russian literature makes a clear distinction between cycling and stalling e.g.
"Так вот при большой размерности матрицы, порядка 20 строк на 100 столбцов, симплекс начинает зацикливаться. В одной книге прочитал, что можно бороться с зацикливанием с помощью модификации симплекс-метода: лексикографический симплекс-метод. Немного переписал программу как было написано в книге. Стало меньше зацикливаться, но полностью не прекратилось."
Ukraine
careful, caring, and perfectionist
Native in: Russian 
, Ukrainian
Works in: English to Russian, Russian to English, Ukrainian to English, and 1 more.
замедление
| И Вам спасибо, Ник. |
Discussion
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. Замечания о сложности решения ЗЛП).
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.