python linear-programming glpk integer-programming

Programación lineal de enteros mixtos de Python



linear-programming glpk (1)

Pulp es una interfaz de modelado de python que se conecta a solucionadores como CBC (código abierto), CPLEX (comercial), Gurobi (comercial), XPRESS-MP (comercial) y YALMIP (código abierto).

También puede usar Pyomo para modelar el problema de optimización y luego llamar a un solucionador externo, a saber, CPLEX, Gurobim GLPK y la biblioteca de solucionadores AMPL.

También puede llamar a GLPK desde GLPK/Python , PyGLPK o PyMathProg .

Otro lenguaje de modelado es CMPL , que tiene una interfaz de python para solucionadores de MIP (solo para programas lineales).

Todos los solucionadores anteriores resuelven programas lineales de enteros mixtos , mientras que algunos de ellos (CPLEX, GUROBI y XRESS-MP, por supuesto) pueden resolver programas cuadráticos de enteros mixtos y programas cuadráticos restringidos cuadráticamente (y también programas cónicos, pero esto probablemente va más allá del alcance de esto pregunta).

MIP se refiere a programas enteros mixtos, pero se usa comúnmente para referirse solo a programas lineales. Para hacer la terminología más precisa, uno siempre debe referirse a MILP o MINLP (Programación no lineal entera mixta).

Tenga en cuenta que CPLEX y GUROBI también tienen sus propias API de Python, pero ellos (y también) XPRESS-MP son productos comerciales, pero gratuitos para la investigación académica. CyLP es similar a Pulp anterior pero interactúa con los solucionadores COIN-OR CBC y CGL y CLP.

Tenga en cuenta que existe una gran diferencia en el rendimiento de los solucionadores comerciales y gratuitos : estos últimos se están quedando atrás del primero por un amplio margen. SCIP es quizás el mejor solucionador no comercial (ver más abajo para una actualización). Su interfaz de Python, PySCIPOpt, está here .

Además, eche un vistazo a esta pregunta SO .

Finalmente, si está interesado en un solucionador de restricciones simple (no en la optimización), eche un vistazo a python-constraint .

¡Espero que esto ayude!

ACTUALIZACIONES

Más solucionadores e interfaces de Python que cayeron en mi radar:

MIPCL , que parece ser uno de los solucionadores MIP no comerciales más rápidos y rápidos, tiene una interfaz de Python que tiene bastante buena documentación . Sin embargo, MIPCLShell cuenta que la API de Python no incluye la funcionalidad avanzada que se incluye con el MIPCLShell nativo. Me gusta especialmente el manual MIPCL-PY , que muestra una variedad de modelos utilizados en la Gestión de operaciones, además de algunas implementaciones a pequeña escala. Es un manual introductorio muy interesante por derecho propio, independientemente de qué solucionador / API se quiera utilizar.

Herramientas de optimización de Google , que incluyen una multitud de funcionalidades, como

  • Un solucionador de programación de restricciones y un solucionador de programación lineal ( no MIP )
  • Una interfaz para solucionadores de MIP (admite CBC, CLP, GLOP, GLPK, Gurobi, CPLEX y SCIP)
  • Algoritmos especializados para gráficos, para el problema del vendedor ambulante, el problema del enrutamiento del vehículo y para los problemas de embalaje y mochila

Tiene una amplia documentación de varios problemas tradicionales de quirófano e implementaciones simples. No pude encontrar una documentación completa de la API de Python, aunque existen algunos ejemplos here . Para mí no está claro cómo se conectan otros solucionadores en la interfaz y si los métodos de estos solucionadores están disponibles.

CVXOPT , un paquete de código abierto para la optimización convexa, que interactúa con GLPK (código abierto) y MOSEK (comercial). Es versátil, ya que puede abordar muchas clases de problemas (especialmente lineal, de segundo orden, semidefinido, convexo no lineal). La única desventaja es que modelar problemas complejos puede ser engorroso, ya que el usuario necesita pasar los datos de manera "Matlab-y" (es decir, para especificar la matriz, los vectores rhs, etc.). Sin embargo, se puede PICOS desde las interfaces de modelado PICOS y ...

CVXPY , un lenguaje de optimización integrado en Python para problemas de optimización convexa, que contiene CVXOPT como solucionador predeterminado, pero puede conectarse a los solucionadores MIP habituales .

Gracias a RedPanda por señalar que CVXOPT/CVXPY admite solucionadores MIP.

Para obtener un artículo muy completo sobre las capacidades de modelado de optimización de paquetes y lenguajes orientados a objetos (no restringido a Python), consulte este artículo .

¿Hay algún solucionador de programación lineal de enteros mixtos (MILP) para Python?

¿Puede Python GLPK resolver el problema MILP? Leí que puede resolver el problema de los enteros mixtos.
Soy muy nuevo en el problema de programación lineal. Así que estoy bastante confundido y realmente no puedo diferenciar si la Programación de enteros mixtos es diferente de la programación lineal de enteros mixtos (MILP).