Вопрос
Я использую CPLEX для решения огромных моделей оптимизации (более 100 тысяч переменных), теперь я хотел бы посмотреть, смогу ли я найти альтернативу с открытым исходным кодом, я решаю смешанные целочисленные задачи (MILP), и CPLEX отлично работает, но это очень дорого, если мы хочу масштабироваться, поэтому мне действительно нужно найти альтернативу или начать писать собственную специальную библиотеку оптимизации (что будет болезненно)
Любое предложение/понимание будет высоко оценено
Лично я обнаружил, что GLPK лучше (то есть быстрее), чем LP_SOLVE. Он поддерживает различные форматы файлов, а еще одним преимуществом является его библиотечный интерфейс, который обеспечивает плавную интеграцию с вашим приложением.
Еще одно одобрение для COIN-OR. Мы обнаружили, что компонент линейного оптимизатора (Clp) был очень сильным, а смешанный целочисленный компонент (Cbc) можно было довольно хорошо настроить с помощью некоторого анализа. Мы сравнивали с LP-Solve и GLPK.
Для действительно сложных задач подойдет коммерческий решатель.
Попробуйте решатель SCIP. Я использовал его для задач MILP с более чем 300 тыс. переменных с хорошей производительностью. Его производительность MILP намного лучше, чем GLPK. Gurobi также имеет отличную производительность для задач MILP (и обычно лучше, чем SCIP (май 2011 г.)), но это может быть дорого, если вы не являетесь академическим пользователем. Gurobi будет использовать многоядерность для ускорения решателя.
На вашем месте я бы попытался использовать интерфейс с несколькими решателями, такой как Osi (C++) или PuLP (python), чтобы вы могли написать свой код один раз и протестировать его с помощью многих решателей.
Если целочисленные программы, которые вы собираетесь решить, огромны, я бы рекомендовал Python, а не C++, потому что ваш код будет выглядеть чище и 99% времени будет потрачено на решатель.
Если, наоборот, задачи небольшие, то временем на копирование задач из памяти python в решатель (туда и обратно) больше не стоит пренебрегать: в этом случае можно поэкспериментировать с заметными улучшениями производительности, используя скомпилированный язык .
Но если проблемы чрезвычайно велики, то скомпилированные языки снова выиграют, потому что объем памяти будет примерно разделен на 2 (нет копии проблемы в python).
Вы пробовали lp_solve? Были также некоторые другие предложения в следующих вопросах для Java:
Я рекомендую проверить проект COIN. МОНЕТА ИЛИ
Здесь много хороших решателей, в том числе ipOPT для нелинейных задач, а также пара смешанных целочисленных решателей.
Scip неплох!
Хотя, возможно, это не то, что вы хотите услышать, но между коммерческими решателями CPLEX и Gurobi, с одной стороны, и решателями с открытым исходным кодом, с другой стороны, есть световые годы.
Тем не менее, вам может повезти, и ваша модель отлично работает с GLPK, Coin или подобными, но в целом решения с открытым исходным кодом сильно отстают от коммерческих решателей. Если бы было иначе, никто бы не стал платить 12 000$ за лицензию Gurobi и уж тем более за лицензию CPLEX.
В последние годы я видел много-много моделей, которые были слишком сложны для решателей с открытым исходным кодом. Поверьте мне...
Дело не столько в размере, сколько в численной сложности.
Я удивлен, что никто не упомянул 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).
В тесте Mixed Integer Linear Programming Benchmark с 12 потоками и ограничением по времени в 2 часа MIPCL удалось решить 79 случаев. Только коммерческие решатели CPLEX, Gurobi и XPRESS смогли решить больше при заданных ограничениях (86 или 87 экземпляров соответственно).
Также с точки зрения выбранной метрики производительности (опять же с использованием 12 потоков) MIPCL быстрее, чем проверенные производные SCIP (FSCIPC, FSCIPS) и решатель с открытым исходным кодом CBC. Опять же, только коммерческие решатели CPLEX, Gurobi и XPRESS значительно превосходят MIPCL с точки зрения производительности.
100 тысяч переменных - это большая проблема. Многие библиотеки с открытым исходным кодом плохо работают с таким количеством переменных. Из того, что я читал, lp_solve был протестирован только для около 30 тысяч переменных. Использование коммерческой системы может быть вашим единственным выбором.
Я использовал DICOPT с сервером NEOS (http://www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html) для решения больших (приблизительно 1 тыс. переменных и 1 тыс. ограничений) смешанных целочисленных нелинейных программ и нашел его превосходным.
Для моей задачи DICOPT справился намного лучше, чем другие решатели MINLP, перечисленные на сервере neos BARON/KNITRO/LINDO/SBB и т. д.
Существуют определенные ограничения для отправки заданий в NEOS, и это немного обременительно, но бесплатный доступ к мощному коммерческому решателю более чем компенсирует это.
Я добавлю следующее к уже отличным ответам.
Хотя, как отмечали другие, коммерческие решатели намного быстрее и эффективнее, чем бесплатные альтернативы, важно учитывать, какой разрыв в оптимальности вы можете принять. Для больших задач со многими целочисленными переменными вы можете получить гораздо более быстрое время решения, если вы можете принять 1% или даже больше разрыва оптимальности (по умолчанию, как правило, около 0,01% или меньше).
Конечно, если вы решаете проблему, в которой 1% составляет миллионы долларов, это неприемлемо - отсюда и рынок первоклассных решателей. (Некоторые сравнения Gurobi с бесплатными решателями здесь)
Я согласен с другими в том, что использование платформы, которая генерирует независимые от решателя файлы задач (например, файлы *.mps, *.lp), имеет смысл, поскольку затем вы можете попробовать другие решатели. Я использую PuLP и нахожу его , и бесплатный решатель COIN_CBC, отлично. Хотя и ограничен для задач со многими целочисленными переменными.
Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.
