О практике преждевременного прерывания

[Andrey_Kireew]

Широко известно, что наиболее трудоёмкой операцией модифицированного симплекс-алгоритма (метод обратной матрицы) является вычисление элементов обновленной строки функционала, на основании которых принимается решение о выборе разрешающего столбца. В этих условиях, проверка всех элементов функционала становится очень накладной и возникает соблазн преждевременного её прерывания, не дожидаясь фатального финала.
В литературе часто можно встретить, на мой взгляд чрезмерно осторожные рекомендации, о прекращении дальнейшей проверки после обнаружения первого отрицательного значения. Лично я уже неоднократно следовал этой рекомендации, и постоянно терпел неудачи. Сходимость процесса оптимизации при этом как правило резко ухудшается, и кроме этого - возникает ряд дополнительных проблем. Самое неприятное - это псевдозацикливание, когда в функционале, из-за ошибок округления постоянно появляются очень маленькие отрицательные элементы, которые алгоритм пытается обратно "запихать" в базис. Так может продолжаться бесконечно, и традиционные методы борьбы с зацикливанием мало помогают.
Единственное работающее решение, которое я нашел - введение малого порога, для отсева ошибок округления. Но это не панацея, т.к. определение оптимального порога само по себе представляет проблему. При слишком большой его величине, оптимизация до конца может так и не дойти. И при всём при этом - сходимость всё равно очень медленная.
При полном переборе всего функционала, такой проблемы нет. Скорость сходимости удовлетворительная, и всё работает надёжно. Однако, вычислительные затраты велики, и общее время оптимизации получается сопоставимо с первым вариантом.
В связи с этим, у меня возникла идея определить некий оптимальный критерий прерывания проверки, промежуточный между этими двумя крайними случаями. Я перепробовал много разных способов. Например, выбирать не первый попавшийся отрицательный элемент, а элемент, если ранее него было найдено не менее k больших отрицательных элементов. Или, искать минимальный отрицательный элемент, но после нахождения каждого нового отрицательного элемента, сокращать диапазон поиска (делением на константу, или вычитанием константы). Все они дают определённый эффект и позволяют снизить общее время вычислений в несколько раз. Но здесь есть одна проблема - для разных задач существует своё оптимальное значение параметра прерывания, определить которое наперёд я затрудняюсь.

В связи со сложившейся ситуацией, убедительная просьба всем участникам форума, предоставить посильную помощь в решении данной проблемы. Возможно, кто то владеет информацией по данной тематике. В википедии я встречал только информацию о методе порогов, но ничего конкретного об этом так и не нашел

[пианист]

Не скажу, что понял, но: если речь идёт о прерывании итераций, почему бы не пойти стандартным путем, оценивать, сколько не дошли до оптимального значения(гэп)? по целевой функции, имею в виду..

[Andrey_Kireew]

пианист в сообщении #1451546 писал(а):

если речь идёт о прерывании итераций

Да нет, речь здесь о выборе очередного направления оптимизации. В данном случае его выбор сводится к выбору вводимой в базис переменной.

С прерыванием самого итеративного процесса как раз особых проблем не возникает. Так как метод конечный, в этом просто нет особой необходимости.

[пианист]

Статья Махорина, п.4.3, не оно?

[Andrey_Kireew]

пианист в сообщении #1452249 писал(а):

не оно?

Спасибо, хорошая статья, но нет - не оно. Там всё больше о вырожденности базиса, и связанные с этим вопросы.
Мой вопрос - о снижении вычислительных затрат за счёт ограничения числа проверяемых симплекс-оценок.

Опытным путём я обнаружил, что определение разрешающего столбца по результатам проверки 10-20% от общего числа симплекс-оценок, почти не приводит к увеличению количества итераций, но существенно снижает вычислительные затраты, а как следствие - и общее время работы алгоритма. Но есть тонкость - положение проверяемого фрагмента от одной итерации к другой, должно всё время меняться по определённому алгоритму. Понятно, что если каждый раз проверять один и тот же фрагмент, результат будет плачевный.

Конечно, многое зависит от реализации алгоритма. На своём примере, я обнаружил, что выгодно дополнительное уменьшение размеров проверяемого фрагмента, вплоть до 10-20% от общего числа ограничений задачи (в моём случае, число ограничений намного меньше числа переменных). Число итераций при этом увеличивается в 1,5-2 раза, но за счёт снижения трудоёмкости одной итерации, получается дополнительный выигрыш производительности. Это лучшее, чего мне удалось добиться. Эта стратегия устойчиво работает на широком круге задач. К стати, если в задаче всего 10-20 ограничений, то выбор разрешающего столбца по первому попавшемуся отрицательному элементу, становится оптимальным. Однако, если число ограничений значительно больше, число итераций при этом подходе становится слишком большим, и предпочтительно проверять сразу несколько оценок.

Не могу не отметить, описанные в предоставленной Вами статье, альтернативные методы выбора разрешающего столбца: метод крутого ребра и метод Харрис, позволяющие дополнительно ускорить сходимость симплекс метода, по сравнению с традиционным методом Данцига. Ранее, я с ними встречался в книге Мутаф Б, но в этой статье они изложены понятнее. Но там не идёт речи ни о каком преждевременном прерывании - напротив, требуются дополнительные вычисления, которые как заявление компенсируются сокращением числа итераций. Уж не знаю как оно на самом деле, возможно, как нибудь проверю. Ведь эффективность всех этих приёмов очень сильно зависит от особенностей конкретных задач.