Python Смешанное Целочисленное Линейное Программирование

Пульпа это интерфейс моделирования python, который подключается к решателям, таким как CBC(открытый исходный код), CPLEX (коммерческий), Гуроби(коммерческий), XPRESS-MP(коммерческий) и ЯЛМИП(open source).

Вы также можете использовать Пиомо для моделирования задачи оптимизации и последующего вызова внешнего решателя, а именно CPLEX, Gurobim GLPK и библиотеки AMPL solver.

Вы можете также звоните ГЛПК из GLPK / Python, Пиглпк или PyMathProg.

Еще одним языком моделирования является CMPL, который имеет интерфейс python для решателей MIP (только для линейных программ).

Все вышеперечисленные решатели решают смешанные целочисленные линейные программы, в то время как некоторые из них (CPLEX, GUROBI и XRESS-MP наверняка) могут решать смешанные целочисленные квадратичные программы и квадратично ограниченные квадратичные программы (а также конические программы, но это, вероятно, выходит за рамки данного вопроса).

MIP относится к смешанным целочисленным программам, но обычно используется только для обозначения линейных программ. Для уточнения терминологии всегда следует обращаться к MILP или MINLP (смешанное целочисленное нелинейное Программирование).

Обратите внимание, что CPLEX и GUROBI также имеют свои собственные API python, но они (а также) XPRESS-MP являются коммерческими продуктами, но бесплатно для академических исследований. CyLP похож на Pulp выше, но взаимодействует с монетами-или решателями CBC и CGL и CLP.

Обратите внимание, что существует большая разница в производительности коммерческих и свободных решателей : последние отстают от первых с большим отрывом. SCIP is возможно, лучший некоммерческий решатель (смотрите ниже для обновления). Его интерфейс python, PySCIPOpt, является здесь.

Также взгляните на этот так называемый вопрос.

Наконец, если вас интересует простой решатель ограничений (не оптимизация), то посмотрите на python-ограничение.

Надеюсь, это поможет!

Обновления

Другие решатели и интерфейсы python, которые попали в мой радар:

MIPCL , который, по-видимому, является одним из самых быстрых самых быстрых некоммерческих решателей MIP, имеетpython интерфейс , который имеет довольнохорошую документацию . Обратите внимание, однако, что Python API не включает расширенные функциональные возможности, которые поставляются вместе с собственнымMIPCLShell . Мне особенно нравится руководствоMIPCL-PY , которое демонстрирует множество моделей, используемых в управлении операциями, поверх некоторых мелкомасштабных реализаций. Это очень интересное вводное руководство само по себе, независимо от того, какой решатель / API вы можете захотеть использовать.

Инструменты оптимизации Google , которые включают множество функциональных возможностей, таких как

• решатель программирования ограничений и линейное программирование (не MIP) решатель
• интерфейс для решателей MIP (поддерживает CBC, CLP, GLOP, GLPK, Gurobi, CPLEX и SCIP)
• специализированные алгоритмы для графов, для задачи коммивояжера, задачи маршрутизации транспортных средств и для упаковки и рюкзака Бин проблемы

Он имеет обширную документацию нескольких традиционных или проблем и простых реализаций. Я не смог найти полную документацию по API Python, хотя здесь есть некоторые примеры . Мне несколько неясно, как другие решатели подключаются к интерфейсу и доступны ли методы этих решателей.

CVXOPT , пакет с открытым исходным кодом для выпуклой оптимизации, который взаимодействует с GLPK (open source) и MOSEK (коммерческий). Он универсален, поскольку может решать многие классы задач (в частности, линейные, второго порядка, полуопределенные, выпуклые нелинейные). Единственным недостатком является то, что ИТ-моделирование сложных задач может быть громоздким, так как пользователю необходимо передавать данные в "Matlab-y" (т. е. указывать матрицу, векторы rhs и т. д.). Однако его можно вызвать из интерфейсов моделирования PICOS и...

CVXPY , встроенный в python язык оптимизации для выпуклой оптимизации задачи, которая содержит CVXOPT в качестве решателя по умолчанию, но может подключаться к обычным решателям MIP.

Спасибо RedPanda что CVXOPT/CVXPY Поддержка решателей МИП, а также.

Для очень полной статьи о возможностях оптимизационного моделирования пакетов и объектно-ориентированных языков (не ограничиваясь Python), проверьте эту статью.