Лучший решатель для оптимизации смешанных целых чисел с открытым исходным кодом [закрыт]

Question

Я использую CPLEX для решения огромных моделей оптимизации (более 100 тыс. переменных), теперь я хотел бы посмотреть, смогу ли я найти альтернативу с открытым исходным кодом, я решаю задачи со смешанными целыми числами (MILP), и CPLEX отлично работает, но это очень дорого, если мы хотим масштабироваться, поэтому мне действительно нужно найти альтернативу или начать писать нашу собственную библиотеку оптимизации ad-hoc (что будет болезненно)

Любое предложение / проницательность были бы высоко оценены

Answer 1

Я лично нашел GLPK ( ГЛПК ) лучше (т.е.быстрее), чем LP_SOLVE.Он поддерживает различные форматы файлов, и еще одним преимуществом является его библиотечный интерфейс, который обеспечивает плавную интеграцию с вашим приложением.

Answer 2

Еще одно одобрение для МОНЕТА-ИЛИ.Мы обнаружили, что компонент линейного оптимизатора (Clp) был очень сильным, а компонент смешанного целого числа (Cbc) можно было бы довольно хорошо настроить с помощью некоторого анализа.Мы сравнили с LP-Solve и GLPK.

Для решения действительно сложных проблем лучше всего обратиться к коммерческому решателю.

Answer 3

Попробуйте SCIP-решатель.Я использовал его для решения задач MILP с более чем 300 тысячами переменных с хорошей производительностью.Его производительность MILP намного лучше, чем у GLPK.Gurobi также обладает отличной производительностью для решения задач MILP (и, как правило, лучше, чем SCIP (май 2011)), но это может оказаться дорогостоящим, если вы не являетесь академическим пользователем.Gurobi будет использовать многоядерные процессоры для ускорения работы решателя.

Answer 4

Вы пробовали lp_solve?В следующих вопросах были также некоторые другие предложения для Java:

• библиотека математической оптимизации для Java - бесплатные рекомендации или рекомендации с открытым исходным кодом?
• Инструмент линейного программирования / Библиотеки для Java

Answer 5

На вашем месте я бы попытался использовать интерфейс с несколькими решателями, такой как Osi (C ++) или PuLP (python), чтобы вы могли написать свой код один раз и протестировать его со многими решателями.

Если целочисленные программы, которые вы собираетесь решать, огромны, я бы рекомендовал python вместо C ++, потому что ваш код будет выглядеть чище и 99% времени будет потрачено на решатель.

• https://projects.coin-or.org/Osi
• http://code.google.com/p/pulp-or/

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

Но если проблемы в подавляющем большинстве огромны, то скомпилированные языки снова выиграют, потому что объем памяти будет примерно разделен на 2 (в python проблема не повторяется).

Answer 6

Я рекомендую ознакомиться с проектом COIN.МОНЕТА ИЛИ

Здесь много хороших решателей, включая ipOPT для нелинейных задач и пару также смешанных целочисленных решателей.

Answer 7

Сцип это совсем не плохо!

Answer 8

Хотя, возможно, это не то, что вы хотите услышать, но между коммерческими решателями CPLEX и Gurobi, с одной стороны, и решателями с открытым исходным кодом, с другой стороны, световые годы.

Тем не менее, вам может повезти, и ваша модель прекрасно работает с GLPK, Coin или чем-то подобным, но в целом решения с открытым исходным кодом сильно отстают от коммерческих решателей.Если бы все было по-другому, никто бы не платил 12.000 долларов за лицензию Gurobi и еще больше за лицензию CPLEX.

За последние годы я видел много-много моделей, которые были слишком сложны для решателей с открытым исходным кодом.Поверь мне...

Дело не столько в размере, сколько в сложности вычисления.

Answer 9

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

Answer 10

Я использовал DICOPT, используя сервер NEOS (http://www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html) для решения больших (приблизительно 1k переменных и 1k ограничений) смешанных целочисленных нелинейных программ и нашел это превосходным.

Для моей проблемы DICOPT справился намного лучше, чем другие решатели MINLP, перечисленные на сервере neos BARON / KNITRO / LINDO / SBB и т.д.

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

Answer 11

Я добавлю следующее к уже отличным ответам.

Хотя, как отмечали другие, коммерческие решатели намного быстрее и эффективнее бесплатных альтернатив, важно учитывать, с каким разрывом в оптимальности вы можете согласиться.Для больших задач со многими целочисленными переменными вы можете добиться гораздо более быстрого решения, если сможете принять разрыв в оптимальности в 1% или даже больше (значения по умолчанию, как правило, составляют около 0,01% или меньше).

Конечно, если вы решаете проблему, где 1% выражается в миллионах долларов, это неприемлемо - отсюда рынок первоклассных решателей.(Некоторые сравнения Gurobi со свободными решателями здесь)

Я бы согласился с другими, что использование платформы, которая генерирует файлы задач, не зависящие от решателя (такие как файлы * .mps, *.lp), имеет смысл, поскольку затем вы можете попробовать другие решатели.Я использую Мякоть и я нахожу это, как и бесплатный решатель COIN_CBC, отличным.Хотя и ограничен для задач со многими целочисленными переменными.

Answer 12

Я удивлен, что никто не упомянул MIPCL (http://www.mipcl-cpp.appspot.com/index.html).Этот решатель утверждает, что имеет открытый исходный код по лицензии LGPL (исходный: http://www.mipcl-cpp.appspot.com/licence.html), таким образом, он также подходит для использования в приложениях без открытого исходного кода.Но чего не хватает для того, чтобы быть действительно открытым исходным кодом, так это исходного кода самого решателя.

Ханс Миттельманн совсем недавно (10 сентября 2017) провел тест по смешанному целочисленному линейному программированию: http://plato.asu.edu/ftp/milpc.html (вам также может быть интересно взглянуть на обзорную страницу http://plato.asu.edu/bench.html или слайды из его выступления: http://plato.asu.edu/talks/informs2017.pdf).

В тесте смешанного целочисленного линейного программирования с 12 потоками и ограничением по времени в 2 часа MIPCL удалось решить 79 примеров.Только коммерческим решателям CPLEX, Gurobi и XPRESS удалось решить больше при заданных ограничениях (86 или 87 экземпляров соответственно).

Также с точки зрения выбранной метрики производительности (опять же с использованием 12 потоков) MIPCL быстрее, чем проверенные производные SCIP (FSCIPC, FSCIPS) и решатель CBC с открытым исходным кодом.И снова только коммерческие решатели CPLEX, Gurobi и XPRESS значительно превосходят MIPCL по производительности.

Answer 13

Не с открытым исходным кодом, но если у вас есть лицензия Microsoft Academic Alliance, Microsoft Решающий Фонд (MSF) корпоративная версия включена в комплект поставки. Гуроби также бесплатно для академических целей, я использовал его в своем дипломном исследовании.