Какое самое быстрое программное обеспечение (с открытым исходным кодом) для решения задачи смешанного целочисленного программирования

14

У меня смешанная проблема целочисленного программирования. И я в настоящее время использую GLPK в качестве моего решателя. Но я обнаружил, что GLPK хорош для задачи линейного программирования, но для программирования со смешанным целым числом это требует гораздо большего времени, поэтому не отвечает нашим требованиям. Я так ищу другое программное обеспечение. Есть ли другие хорошие инструменты с открытым исходным кодом для быстрого решения проблемы смешанного целочисленного программирования? Благодарность!

Ю Хао
источник
Вы видели сравнение со SCIP ?
Али

Ответы:

14

Если вы хотите что-то с открытым исходным кодом, вы, вероятно, захотите попробовать CBC-код COIN (у них также есть пара других решателей MILP, таких как платформа с разветвлением и ценой или SYMPHONY).

Gurobi и CPLEX будут значительно быстрее, и на совещании INFORMS 2011 или 2012 года Gurobi был быстрее CPLEX (хотя показатели производительности, конечно, зависят от проблем). На MILP, решенных в моей диссертации, Gurobi был примерно в 15-100 раз быстрее, чем CBC, а CPLEX был почти так же быстро, как Gurobi, но немного медленнее (например, в 12-80 раз быстрее).

Хотя производительность в худшем случае действительно экспоненциальная, время выполнения будет сильно зависеть от структуры проблемы. Маловероятно, что вы сможете решить MILP с миллионами переменных, если не будете использовать специальную структуру (возможно, если это стохастическая программа, которая может быть разложена на множество гораздо более мелких задач), но вполне возможно решить нетривиальные MILP с тысячами переменные менее чем за минуту. (Конечно, эти проблемы также могут занять час или больше.)

Как отмечает Брайан Борчерс, у CPLEX и Gurobi есть бесплатные лицензии, доступные для некоторых исследователей, и один из этих двух пакетов программного обеспечения будет действительно лучшим для использования в качестве универсального решателя MILP.

Джефф Оксберри
источник
6

Смешанные целочисленные задачи линейного программирования решить гораздо сложнее, чем задачи линейного программирования. С точки зрения вычислительной сложности, LP могут быть решены за полиномиальное время, в то время как решение MILP является проблемой NP-Hard. Известные алгоритмы решения MILP имеют экспоненциальную сложность в наихудшем случае.

Существуют и другие пакеты программного обеспечения для смешанного целочисленного линейного программирования, в том числе SCIP (бесплатный для академического использования), CPLEX (коммерческий, но с академическим лицензированием) и GUROBI (также коммерческий с академическим лицензированием.) Один или несколько из этих пакетов может быть значительно быстрее, чем GLPK в ваших задачах, но не ожидайте, что какой-либо из них будет так же быстр в решении MILP, как в решении LP такого же размера.

Брайан Борхерс
источник
4

Если вы хотите попробовать кучу разных решателей, попробуйте модель моделирования JuMP Джулии . Это позволяет вам написать вашу модель как модель JuMP, а затем переключить решатели одной строкой кода. Например, для задач MILP вы можете выбрать из решателей Bonmin, Cbc, Couenne, CPLEX, GLPK, Gurobi и MOSEK. По этой причине, если вы напишите это в JuMP, вы можете просто попробовать все решатели, упомянутые Джеффом, и посмотреть, что работает, без необходимости писать кучу кода. Ваши личные тесты станут лучшим источником знаний о том, какие алгоритмы для ваших задач являются самыми быстрыми.

Крис Ракауцкас
источник
Добавляет ли среда JuMP много накладных расходов?
naught101
1
Нет, JuMP выполняется с помощью макросов, поэтому во время компиляции. Фактически, то, что JuMP использует, это использует макросы для переписывания кода и использования авто-дифференциации для вычисления эффективных функций для градиентов, якобианов и гессианов, так что это будет быстрее в тех случаях, когда в противном случае вы не предоставили бы аналитическую форму для градиента / якобиан / гессиан. На самом деле вы можете проверить через, @code_llvmчтобы проверить полученный код сборки, чтобы увидеть, что клейкий код по сути ничего (это также потому, что Джулия наивно использует указатели функций и те же битовые массивы, что и C / Fortran).
Крис Ракауцкас
@ChrisRackauckas Какой решатель работает лучше для нелинейных задач с нелинейными ограничениями?
Скан
Это совершенно другой вопрос, если его, вероятно, не следует задавать в комментарии, но я склонен использовать JuMP с NLopt или IPOPT в зависимости от требуемых ограничений и необходимости глобальной или локальной оптимизации.
Крис Ракауцкас
3

Следуя советам других, я использовал (коммерческий) GAMS для многих проектов. Это очень прямо; все, что вам нужно сделать, это поставить математическую формулировку вашей проблемы. Он собирает переменные, ограничения, целевые функции и все входные данные. Затем он предоставляет ряд решателей (оптимизаторов) для любого случая. В зависимости от вашего случая, вы добавляете более сложные решатели.

Конечно, EASY стоит посмотреть. Фреймворк с открытым исходным кодом.

Термин «быстрый» очень расплывчатый! Вы должны быть более конкретными; Быстро с точки зрения количества итераций? количество оценок? пройденное время? сочетание этих?

Однако, если вы не ищете программное обеспечение и просто хотите решить эту проблему, я мог бы предложить использовать глобальный оптимизатор NSGA-II, который является оптимизатором с открытым исходным кодом с очень высокой репутацией и производительностью.

Если бы вы предоставили больше информации, я мог бы точно ориентироваться.

T3rmInAt0r
источник
1
Вы должны серьезно рассмотреть [openMDAO] [1], который разработан / поддерживается НАСА и является достаточно гибким!
T3rmInAt0r