Interior point method vs Simplex method

[_hum_]

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

[пианист]

Хорошо работает потому что.
Не в полиномиальности счастье ;)

[_hum_]

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

Не в полиномиальности счастье ;)

"Ты что с ума сошел? А в чем же еще!" (с) Карлсон :)

[пианист]

(Оффтоп)

Символично, кстати, что в оригинале этой фразы нет (и сцены), она есть только в мульте.

[mserg]

Одна из причин - частично-целочисленное линейное программирование. Там больших задач не порешаешь, и симплекс-метод вписывается лучше в алгоритм ветвей, границ и отсечений. Дело, видимо, не только в базисах, с которых стартуют "узлы", но и в возможностях по эвристикам и отсечениям.

А эффективная реализация на практике метода внутренней точки - это дорогой коммерческий продукт. И с ходу не соображу, может ли быть равенств больше чем переменных ... Для симплекс-метода это не проблема; он обнаружит конфликт, или обнаружит и исключит линейно зависимые строки.

В свое время находил тестовую библиотеку больших mps-файлов (помню, один из них был точно больше гигабайта) и пробовал их на решателях CBC, GLPK, CPLEX (выбирал метод внутренней точки). В CPLEX, по-моему, метод назывался "барьерных функций". Но, не суть, CPLEX порвал самую большую задачу как тузик грелку. Бесплатные не справились. Задачи по-проще, CBC решал заметно лучше GLPK, но значительно хуже CPLEX.

Также сравнивал симплекс метод и метод внутренней точки для CBC и CPLEX. Для CBC особых различий между решением симплекс-методом и методом внутренней точки обнаружено не было, в CPLEX на больших задачах метод внутренней точки существо был лучше.

Наверняка есть обзоры на эту тему, а бесплатные продукты можно попробовать на тестовых задачах.

[Евгений Машеров]

Потому, что на реальных задачах симплекс-метод работает быстрее. Его "неполиномиальность" состоит в том, что существуют весьма вычурные задачи, в которых время работы экспоненциально. Но они на практике и не встречаются.