Выбор метода решения транспортной задачи

[Grantorino]

Добрый день!
Какой из методов (симплекс, двойственное симплекс, метод внутренней точки, метод потенциалов, другие методы) эффективнее при решении ЗЛП произвольного размера, с количеством переменных 1млн+
Как мне видится, это просто симплекс. Но не понимаю в чем отличие например метода потенциалов от двоейственного или метода внутренней точки.

[Andrey_Kireew]

Grantorino в сообщении #1437241 писал(а):

Но не понимаю в чем отличие например метода потенциалов от двоейственного или метода внутренней точки

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

[dmd]

Думается, сегодня надо не метод выбирать, а солвер из числа существующих, в которых все возможные методы уже реализованы. Если под задачу есть соответствующий бюджет, то выбрать один из коммерческих Gurobi/Cplex/Xpress/SAS (имхо, Гуроби из которых самый эффективный на сегодня). Если бюджета нет, то выбрать один из свободных солверов SCIP/CBC/Lpsolve. Самостоятельно повторить эффективный симплекс в своём коде - задача на пол-жизни, безсмысленно это. Плюс выбрать язык мат-моделирования и соответствующий пакет: коммерческие AMPL/IBM_Cplex_Studio/SAS/Xpress, свободные MiniZinc/Google_OR-Tools/SCIP. У большинства солверов есть Python-API, т.е. в качестве языка мат-моделирования можно выбрать Python.

Andrey_Kireew в сообщении #1441901 писал(а):

... полиномиальную сложность. У симплекс метода она экспоненциальная...

Это не однозначно. Считается, что симплекс экспоненциален в самом худшем случае, когда мат-модель примитивная и не повезло с seed-параметром солвера. В остальных случаях симплекс как минимум суб-экспоненциален, и как максимум полиномиален. Показателен прошедший недавно Kaggle-конкурс Santa 2019 с 3.5 млн переменных. Лидеры получали глобальный оптимум шлифовкой мат-модели для коммерческих солверов. Вроде бы ни кто на свободных солверах или своём коде не попал в лидеры.

[Andrey_Kireew]

dmd в сообщении #1441994 писал(а):

Считается, что симплекс экспоненциален в самом худшем случае, когда мат-модель примитивная и не повезло с seed-параметром солвера. В остальных случаях симплекс как минимум суб-экспоненциален, и как максимум полиномиален

Не понимаю, какой смысл Вы вкладываете в понятие "примитивная модель"? Модель определяется конкретной задачей, она такая - какая есть. Проблемы, связанные с некорректной формулировкой задачи связывать с недостатками метода оптимизации, не совсем уместно.

В целом да, экспоненциальная сложность - это самый худший случай, но и полиномиальная - практически недостижима. Обычно, что то по середине и на больших задачах метод внутренней точки гарантированно выигрывает (большая задача - это несколько тыс. ограничений и более). Лично у меня, на числе 5000 тыс. симплекс уже начинает "захлёбываться", и затем его сложность растёт катастрофически. Это методическая проблема, она не решается оптимизацией кода и наращиванием вычислительной мощности. Да, число переменных, действительно, влияет не так сильно, хотя цифра 3,5 млн. впечатляет.

К стати Grantorino, если число ограничений намного больше числа переменных, имеет смысл перейти к двойственной задаче, в которой переменные и ограничения меняются местами.

[feedinglight]

Какие-то тесты гуглятся: http://plato.asu.edu/bench.html