Я заинтересован в реализации SM для задачи LP, однако я слышал о возможных подводных камнях: книга Кормена говорит, что возможно иметь входные данные, которые приведут к тому, что наивная реализация будет вести себя экспоненциально. Я также слышал, что наивная реализация может зацикливаться на каких-то данных.
Есть ли книга / бумага / источник, объясняющий нюансы практической реализации СМ?
Заранее спасибо.
Ответы:
Я настоятельно рекомендую статью Биксби, «отца» CPLEX, в которой рассматриваются не только аспекты реализации (пересмотренного) симплексного алгоритма: Роберт Э. Биксби , « Решение реальных линейных программ: десятилетие и более прогресса , операции» Исследования (50) 2002, 3-15 .
источник
Симплексный алгоритм отсутствует в P. CLRS, следовательно, утверждает, что, хотя на практике он работает «хорошо», есть некоторые входные данные, заставляющие алгоритм работать в экспоненциальном времени. Это строго связано с алгоритмом, а не с его реализацией: вы столкнетесь с этим независимо от того, как именно вы реализуете алгоритм. Однако LP находится в P. Это было доказано Хачианом в 1979 году, однако его алгоритм эллипсоида не практичен. Сегодня методы внутренних точек широко используются. Первый был обнаружен Кармаркаром в 1984 году.
Если вы заинтересованы в практической реализации, взгляните на:
GUROBI, бесплатный для академического использования, на данный момент является лучшим доступным оптимизатором (как для последовательной, так и для параллельной версий с общей памятью):
http://www.gurobi.com
библиотека GLPK:
http://www.gnu.org/software/glpk/
это проект с открытым исходным кодом, обеспечивающий реализацию для:
источник
В книге Вандербея по линейному программированию рассматриваются многие детали низкого уровня ... Но, как предлагают другие ответы / комментарии, реализация LP Solver - трудная и неблагодарная задача. Вероятно, стоит пойти дальше с решателем ... (Есть также несколько программ с открытым исходным кодом ...)
источник
Это не только наивные реализации, которые иногда ведут себя экспоненциально. На самом деле, я думаю, что все известные детерминированные и рандомизированные правила имеют суперполиномиальные входные данные для наихудшего случая. Большинство известных входных данных, которые приводят к этому наихудшему поведению, имеют высокую степень структурированности, связанный с этим вопрос
Структура патологических случаев для симплексных алгоритмов
Однако на практике СМ работает хорошо. Это было формализовано введением сглаженного анализа, который в основном представляет собой анализ наихудшего случая со слегка возмущенными входными данными. Согласно этому анализу, SM является многопоточным, другими словами, для каждого входа (даже патологического) есть небольшое возмущение, которое позволяет алгоритму работать хорошо. Это понимание было преобразовано в рандомизированный алгоритм, который работает в polytime. Однако, насколько я понимаю, до сих пор идут споры о том, можно ли считать этот алгоритм «истинным» симплексным алгоритмом. Я также не знаю, реализуют ли что-то подобное в стандартных пакетах, но вы сможете найти какую-то реализацию, если будете искать вокруг, потому что результат более 5 лет.
источник
Вы можете проверить Luenberger, Ye, линейное и нелинейное программирование, 3-е изд. Это кажется довольно всеобъемлющим, но я еще не успел сказать, полностью ли он отвечает на ваш вопрос.
источник