Programación lineal en python?

subplot title python

Question

Necesito hacer un modelo de programación lineal. Aquí están las desigualdades que estoy usando (por ejemplo):

6x + 4y <= 24
x + 2y <= 6
-x + y <= 1
y <= 2

Necesito encontrar el área descrita por estas desigualdades y sombrearla en un gráfico, así como hacer un seguimiento de los vértices de las líneas delimitadas de esta área y dibujar la línea delimitadora en un color diferente. Vea el gráfico a continuación para ver un ejemplo de lo que estoy buscando.

.

Estoy usando Python 3.2, numpy y matplotlib. ¿Hay mejores módulos para la programación lineal en Python?

Answer 1

La única vez que se usa un gráfico para resolver un programa lineal es para un problema de tarea. En todos los demás casos, los problemas de programación lineal se resuelven mediante el álgebra lineal de matriz.

En cuanto a Python, si bien hay algunas bibliotecas de Python puras, la mayoría de las personas usan una biblioteca nativa con enlaces de Python. Existe una amplia variedad de librerías gratuitas y comerciales para programación lineal. Para obtener una lista detallada, consulte Programación lineal en Wikipedia o la Encuesta sobre software de programación lineal en OR / MS Today.

Descargo de responsabilidad: Actualmente trabajo para Gurobi Optimization y anteriormente trabajé para ILOG, que proporcionó CPLEX.

Answer 2

Las otras respuestas han hecho un buen trabajo al proporcionar una lista de solucionadores. Sin embargo, solo PuLP se ha mencionado como una biblioteca de Python para formular modelos LP.

Otra gran opción es Pyomo . Al igual que PuLP, puede enviar el problema a cualquier solucionador y leer la solución en Python. También puedes manipular los parámetros del solucionador. Un compañero y yo comparamos el rendimiento de PuLP y Pyomo en 2015 y descubrimos que Pyomo podía generar archivos .LP para el mismo problema varias veces más rápido que PuLP.

Answer 3

Para resolver el problema de programación lineal, puede usar el módulo scipy.optimize.linprog en SciPy, que usa el algoritmo Simplex.

Answer 4

Recomendaría el paquete cvxopt para resolver problemas de optimización convexos en Python. Un breve ejemplo de código Python para un programa lineal se encuentra en la documentación de cvxopt here .

Answer 5

Yo recomendaría usar el paquete de PuLP python. Tiene una interfaz agradable y puede usar diferentes tipos de algoritmos para resolver LP.

Answer 6

lpsolve es lo más fácil para mí. No es necesario instalar solver por separado. Viene con el paquete.

Answer 7

ACTUALIZACIÓN: La respuesta se ha vuelto un tanto obsoleta en los últimos 4 años, aquí hay una actualización. Tienes muchas opciones:

• Si no tiene que hacerlo con Python, es mucho más fácil hacerlo en un lenguaje de modelado , consulte ¿ Alguna buena herramienta para resolver programas de enteros en Linux?

• Personalmente uso Gurobi estos días a través de su API de Python. Es un producto comercial, de código cerrado, pero gratuito para la investigación académica.

• SciPy ofrece programación lineal: scipy.optimize.linprog . (Nunca he probado este).

• Con PuLP puede crear archivos MPS y LP y luego resolverlos con GLPK, COIN CLP / CBC, CPLEX o XPRESS a través de su interfaz de línea de comandos. Este enfoque tiene sus ventajas y desventajas.

• Aparentemente, CVXOPT ofrece una interfaz Python para GLPK , no lo sabía. He estado usando GLPK durante 8 años y puedo recomendar altamente GLPK. Los ejemplos y tutoriales de CVXOPT parecen realmente buenos!

• Puede encontrar otras posibilidades en el Wikilibro bajo GLPK/Python . Tenga en cuenta que muchos de estos no están necesariamente restringidos a GLPK.