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