Лучший с открытым исходным кодом Mixer Integer Optimization Solver
Я использую CPLEX для решения огромных оптимизационных моделей (более 100 тыс. Переменных), теперь я хотел бы посмотреть, смогу ли я найти альтернативу с открытым исходным кодом, я решу смешанные целочисленные задачи (MILP) и CPLEX прекрасно работает, но это очень дорого, если мы хочу масштабировать, поэтому мне действительно нужно найти альтернативу или начать писать собственную специальную библиотеку оптимизации (которая будет болезненной)
Любое предложение / понимание будет высоко ценится
13 ответов
Я лично нашел GLPK лучше (т.е. быстрее), чем LP_SOLVE. Он поддерживает различные форматы файлов, и еще одним преимуществом является его интерфейс библиотеки, который обеспечивает плавную интеграцию с вашим приложением.
Еще одна рекомендация для монеты или. Мы обнаружили, что компонент линейного оптимизатора (Clp) был очень сильным, и смешанный целочисленный компонент (Cbc) можно довольно хорошо настроить с помощью некоторого анализа. Мы сравнили с LP-Solve и GLPK.
Для действительно сложных задач коммерческий решатель - это путь.
Попробуйте решатель SCIP. Я использовал его для проблем MILP с более чем 300K переменных с хорошей производительностью. Его производительность MILP намного лучше, чем GLPK. Gurobi также отлично справляется с проблемами MILP (и, как правило, лучше, чем SCIP (май 2011 г.)), но может оказаться дорогостоящим, если вы не являетесь академическим пользователем. Gurobi будет использовать многоядерные процессоры, чтобы ускорить решение.
На вашем месте я бы попытался использовать интерфейс с несколькими решающими программами, такими как Osi (C++) или PuLP (python), чтобы вы могли написать свой код один раз и протестировать его со многими решателями.
Если целочисленные программы, которые вы собираетесь решать, огромны, я бы порекомендовал python вместо C++, потому что ваш код будет выглядеть чище и 99% времени будет потрачено в решателе.
Если, наоборот, проблемы невелики, то больше не следует пренебрегать временем копирования проблем из памяти Python в решатель (туда и обратно): в этом случае вы можете экспериментировать с некоторыми заметными улучшениями производительности, используя скомпилированный язык,
Но если проблемы чрезвычайно огромны, то скомпилированные языки снова выиграют, потому что объем памяти будет примерно разделен на 2 (нет копии проблемы в python).
Я рекомендую проверить проект COIN. МОНЕТА ИЛИ
Здесь много хороших решателей, включая ipOPT для нелинейных задач и пару смешанных целочисленных решателей.
Ты пытался lp_solve? В следующих вопросах были и другие предложения по Java:
Хотя, возможно, это не то, что вы хотите услышать, но между коммерческими решателями 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), поэтому он также подходит для использования в приложениях с открытым исходным кодом. Но чего не хватает, чтобы быть действительно открытым исходным кодом, так это исходного кода самого решателя.
Ханс Миттельманн (Hans Mittelmann) совсем недавно (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 с точки зрения производительности.
Я добавлю следующее к уже превосходным ответам.
Хотя, как отмечали другие, коммерческие решатели намного быстрее и более эффективны, чем бесплатные альтернативы, важно учитывать, какой разрыв в оптимальности вы можете принять. Для больших задач со многими целочисленными переменными вы можете получить гораздо более быстрое время решения, если вы можете принять 1% или даже больший разрыв в оптимальности (значения по умолчанию, как правило, составляют около 0,01% или менее).
Конечно, если вы решаете проблему, когда 1% переводится в миллионы долларов, это неприемлемо - отсюда и рынок первоклассных решателей. (Некоторые сравнения Gurobi со свободными решателями здесь)
Я согласен с другими, что стоит использовать платформу, которая генерирует независимые от решателя файлы задач (такие как *.mps, *.lp), так как вы можете попробовать другие решатели. Я использую PuLP и нахожу его, и бесплатный решатель COIN_CBC, отлично. Хотя ограничено для проблем со многими целочисленными переменными.
100 тыс. Переменных - большая проблема. Многие из библиотек с открытым исходным кодом плохо работают с таким количеством переменных. Из того, что я прочитал, lp_solve был протестирован только для 30k переменных. Использование коммерческой системы может быть вашим единственным выбором.
Я использовал DICOPT, используя сервер NEOS ( http://www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html) для решения больших (приблизительно 1k переменных и ограничений 1k) смешанных целочисленных нелинейных программ и нашел это отлично.
Для моей проблемы DICOPT сделал намного лучше, чем другие решатели MINLP, перечисленные на neos сервере BARON/KNITRO/LINDO/SBB и т. Д.
Существуют определенные ограничения при отправке заданий в NEOS, и это немного громоздко, но бесплатный доступ к мощному коммерческому решателю более чем компенсирует это.
Не с открытым исходным кодом, но если у вас есть лицензия Microsoft Academic Alliance, в нее входит корпоративная версия http://code.msdn.microsoft.com/solverfoundation (MSF). Gurobi также бесплатен для академических целей, я использовал его в своей диссертации.