Есть ли решение для смешанного целочисленного линейного программирования (MILP) для Python?
Может ли python GLPK решить проблему MILP? Я читал, что он может решить проблему смешанного целого.
Я очень новичок в проблеме линейного программирования. Поэтому я довольно смущен и не могу отличить, если смешанное целочисленное программирование отличается от смешанного целочисленного линейного программирования (MILP).
Pulp - это интерфейс моделирования python, который подключается к решателям, таким как CBC (open source), CPLEX (коммерческий), Gurobi (коммерческий), XPRESS-MP (коммерческий) и YALMIP (с открытым исходным кодом).
Вы также можете использовать Pyomo для моделирования проблемы оптимизации, а затем вызвать внешний решатель, а именно CPLEX, Gurobim GLPK и библиотеку решателей AMPL.
Вы также можете вызвать GLPK из GLPK/Python, PyGLPK или PyMathProg.
Еще одним языком моделирования является CMPL, который имеет интерфейс python для решателей MIP (только для линейных программ).
Все вышеперечисленные решатели разрешают смешанные целые линейные программы, в то время как некоторые из них (CPLEX, GUROBI и XRESS-MP наверняка) могут решать смешанные целочисленные квадратичные программы и квадратичные квадратичные программы (а также конические программы, но это, вероятно, выходит за рамки этого вопрос).
MIP относится к смешанным целым программам, но обычно используется для обозначения только линейных программ. Чтобы уточнить терминологию, всегда следует ссылаться на MILP или MINLP (смешанное целочисленное нелинейное программирование).
Обратите внимание, что CPLEX и GUROBI имеют свои собственные API-интерфейсы python, но они (а также) XPRESS-MP являются коммерческими продуктами, но бесплатными для академических исследований. CyLP похож на Pulp выше, но взаимодействует с решателями COIN-OR CBC и CGL и CLP.
Обратите внимание, что есть большая разница в производительности коммерческих и бесплатных решателей: последние отстают от первого с большим отрывом. SCIP - это, пожалуй, лучший некоммерческий решатель (см. Ниже обновление). Его интерфейс python, PySCIPOpt, находится здесь.
Кроме того, посмотрите на этот вопрос.
Наконец, если вас интересует простой решатель ограничений (а не оптимизация), посмотрите на ограничение python.
Надеюсь, это поможет!
Больше решателей и интерфейсов python, которые попали в мой радар:
MIPCL, который, как представляется, является одним из самых быстрых некоммерческих решений MIP, имеет интерфейс python, который имеет неплохую документацию. Обратите внимание, однако, что API Python не включает расширенную функциональность, которая поставляется вместе с родным MIPCLShell. Мне особенно нравится руководство MIPCL-PY, в котором демонстрируется массив моделей, используемых в Operations Management, помимо некоторых небольших реализаций. Это очень интересное вводное руководство по своему усмотрению, независимо от того, какой solver/API можно использовать.
Инструменты оптимизации Google, которые включают в себя множество функций, таких как
Он имеет обширную документацию по нескольким традиционным OR-проблемам и простым реализациям. Я не мог найти полную документацию Python API, хотя существуют некоторые примеры здесь. Мне несколько непонятно, как другие решатели подключаются к интерфейсу и доступны ли методы этих решателей.
CVXOPT, пакет с открытым исходным кодом для выпуклой оптимизации, который взаимодействует с GLPK (open source) и MOSEK (коммерческий). Он универсален, так как он может решать многие проблемные классы (особенно линейные, полуопределенные, выпуклые нелинейные). Единственный недостаток заключается в том, что моделирование сложных проблем может быть громоздким, так как пользователю необходимо передать данные в режиме "Matlab-y" (т.е. Указать матрицу, векторы rhs и т.д.). Однако его можно вызвать из интерфейсов моделирования PICOS и...
CVXPY, язык оптимизации, основанный на python, для проблем с выпуклой оптимизацией, который содержит CVXOPT в качестве решателя по умолчанию, но он может подключаться к обычным решателям MIP.
Благодаря RedPanda за то, что CVXOPT/CVXPY поддерживает MIP-решатели.
Для получения очень подробной статьи о возможностях оптимизации моделирования пакетов и объектно-ориентированных языков (не ограничиваясь Python), проверьте эту статью.