43

I need to make a linear programming model. Here are the inequalities I'm using (for example):

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

I need to find the area described by these inequalities, and shade it in a graph, as well as keep track of the vertices of the bounding lines of this area, and draw the bounding line in a different color. See the graph below for an example of what I'm looking for.

image of the points of intersection.

I'm using Python 3.2, numpy, and matplotlib. Are there better modules for linear programming in Python?

Improve this question
6
  • 4
    Step one convert the system of inequalities into matrix form. Commented May 22, 2012 at 8:08
  • 2
    @izomorphius according to wikipedia, linear programming is mathematical optimization: en.wikipedia.org/wiki/Linear_programming Commented May 22, 2012 at 8:21
  • @möter agreed -removing my comment. The mistake is mine not the Op's Commented May 22, 2012 at 8:30
  • Your third equation, -x + x <= 1 is a no-op, since it simplifies to 0 <= 1, which is true for all x and y. Commented May 22, 2012 at 8:59
  • @user24562 Could you please also elaborate the process that you have used for your default code. (using numpy & matplotlib) Commented Aug 29, 2016 at 11:07

8 Answers 8

Reset to default
75

UPDATE: The answer has become somewhat outdated in the past 4 years, here is an update. You have many options:

  • If you do not have to do it Python then it is a lot more easier to do this in a modeling langage, see Any good tools to solve integer programs on linux?

  • I personally use Gurobi these days through its Python API. It is a commercial, closed-source product but free for academic research.

  • With PuLP you can create MPS and LP files and then solve them with GLPK, COIN CLP/CBC, CPLEX, or XPRESS through their command-line interface. This approach has its advantages and disadvantages.

  • The OR-Tools from Google is an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.

  • Pyomo is a Python-based, open-source optimization modeling language with a diverse set of optimization capabilities.

  • SciPy offers linear programming: scipy.optimize.linprog. (I have never tried this one.)

  • Apparently, CVXOPT offers a Python interface to GLPK, I did not know that. I have been using GLPK for 8 years now and I can highly recommend GLPK. The examples and tutorial of CVXOPT seem really nice!

  • You can find other possibilites at in the Wikibook under GLPK/Python. Note that many of these are not necessarily resticted to GLPK.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

use PuLP, its an awesome python interface for GLPK, CPLEX or Gurobi
Anonymous downvotes aren't helping anybody. What is wrong with the answer?
Version 1.1 of PuLP links to a homepage at jeannot.org that my Sophos blocks with "High Risk Website Blocked, Access has been blocked as the threat C2/Generic-A has been found on this website." Sophos's page says it's "Command and Control malware." Has anyone used PuLP? What is your take on this?
@mmorin Thank you, I accepted your edit. It's good to see that people find this answer useful.
I think PuLP should be on top of this list, followed by Google ortools and Pyomo
|
20

I'd recommend the package cvxopt for solving convex optimization problems in Python. A short example with Python code for a linear program is in cvxopt's documentation here.

Improve this answer

Comments

7

The other answers have done a good job providing a list of solvers. However, only PuLP has been mentioned as a Python library to formulating LP models.

Another great option is Pyomo. Like PuLP, you can send the problem to any solver and read the solution back into Python. You can also manipulate solver parameters. A classmate and I compared the performance of PuLP and Pyomo back in 2015 and we found Pyomo could generate .LP files for the same problem several times more quickly than PuLP.

Improve this answer

Comments

6

The only time a graph is used to solve a linear program is for a homework problem. In all other cases, linear programming problems are solved through matrix linear algebra.

As for Python, while there are some pure-Python libraries, most people use a native library with Python bindings. There is a wide variety of free and commercial libraries for linear programming. For a detailed list, see Linear Programming in Wikipedia or the Linear Programming Software Survey in OR/MS Today.

Disclaimer: I currently work for Gurobi Optimization and formerly worked for ILOG, which provided CPLEX.

Improve this answer

2 Comments

Between homework and work there's also passion for learning - I think the first sentence you wrote is out of place...
Which is the fastest for Linear Programming Problems?
4

For solving the linear programming problem, you can use the scipy.optimize.linprog module in SciPy, which uses the Simplex algorithm.

Improve this answer

Comments

2

Here is a graphical representation of the problem, inspired from How to visualize feasible region for linear programming (with arbitrary inequalities) in Numpy/MatplotLib?

Linear Programming

import numpy as np
import matplotlib.pyplot as plt

m = np.linspace(0,5,200)
x,y = np.meshgrid(m,m)
plt.imshow(((6*x+4*y<=24)&(x+2*y<=6)&(-x+y<=1)&(y<=2)&(x>=0)&(y>=0)).astype(int), 
    extent=(x.min(),x.max(),y.min(),y.max()),origin='lower',cmap='Greys',alpha=0.3);
# plot constraints
x = np.linspace(0, 5, 2000)
# 6*x+4*y<=24
y0 = 6-1.5*x
# x+2*y<=6
y1 = 3-0.5*x
# -x+y<=1
y2 = 1+x
# y <= 2
y3 = (x*0) + 2
# x >= 0
y4 = x*0
plt.plot(x, y0, label=r'$6x+4y\leq24$')
plt.plot(x, y1, label=r'$x+2y\leq6$')
plt.plot(x, y2, label=r'$-x+y\leq1$')
plt.plot(x, 2*np.ones_like(x), label=r'$y\leq2$')
plt.plot(x, y4, label=r'$x\geq0$')
plt.plot([0,0],[0,3], label=r'$y\geq0$')
xv = [0,0,1,2,3,4,0]; yv = [0,1,2,2,1.5,0,0]
plt.plot(xv,yv,'ko--',markersize=7,linewidth=2)
for i in range(len(xv)):
    plt.text(xv[i]+0.1,yv[i]+0.1,f'({xv[i]},{yv[i]})')
plt.xlim(0,5); plt.ylim(0,3); plt.grid(); plt.tight_layout()
plt.legend(loc=1); plt.xlabel('x'); plt.ylabel('y')
plt.show()

The problem is missing an objective function so any of the shaded points satisfy the inequalities. If it did have an objective function (e.g. Maximize x+y) then many capable Python solvers can handle this problem. Here is a Linear Programming example in GEKKO that also supports mixed integer, nonlinear, and differential constraints.

from gekko import GEKKO
m = GEKKO(remote=False)
x,y = m.Array(m.Var,2,lb=0)
m.Equations([6*x+4*y<=24,x+2*y<=6,-x+y<=1,y<=2])
m.Maximize(x+y)
m.solve(disp=False)

Large scale LP problems are solved in matrix form or in sparse matrix form where only the non-zeros of the matrices are stored. There is a tutorial on LP solutions with a few examples that I developed for a university course.

Improve this answer

Comments

1

I would recommend using the PuLP python package. It has a nice interface and you can use differenty types of algorithms to solve LP.

Improve this answer

Comments

0

lpsolve is the easiest to me. No need to install separate solver. It comes with in the package.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.