Какой алгоритм оптимизации оптимизации Optimized/Mixed Integer используется?

Question

У меня есть математическая модель, линейное программирование, с огромным количеством переменных решения (> 500K - 1M). Какое программное обеспечение/библиотека с открытым исходным кодом (java) можно использовать для моего требования?

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

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

Answer 1

COIN CLP, вероятно, является одним из наиболее быстрых решений с открытым исходным кодом. На коммерческой арене наиболее часто используемыми высокопроизводительными решателями LP являются Cplex и Gurobi. (Коммерческие предложения в основном бесплатны для ученых, но дороги в противном случае). Эти пакеты имеют как симплексные (первичные, так и двойные) и внутренние точечные алгоритмы. Mosek также стоит упомянуть (по некоторым из моих проблем это очень быстро: он имеет очень хороший решатель точки втулки). Структура модели может принести пользу (первому) симплексному методу, но на практике вы должны это проверить. Все эти пакеты имеют привязки Java.

1 миллион переменных и 5 ограничений не должны быть слишком сложными для этих решателей (число ненулевых элементов равно < 6e6, не так уж плохо).