Source

pplp / blog / blog.html

<html>
<body>
<H1>Playing with Linear Programming on PyPy</H1>
Fancy hi-level interfaces often come with a high runtime overhead
making them slow. Here is an experiment with building such an
interface using constructions that PyPy should be good at
optimizing. The idea is to allow the JIT in PyPy to remove the
overhead introduced by using a fancy high-level python interface
on top of a low-level C interface. The application considered is
<a href="http://en.wikipedia.org/wiki/Linear_programming">Linear
programming</a>. It is a tool used to solve linear optimization
problems. It can for example be used to find the nonnegative values
x, y and z that gives the maximum value of

<p />
<center><div class="eq"><img alt="" src="eqsource1.png" /></div></center>

<p />
without violating the constraints

<p />
<center><div class="eq"><img alt="" src="eqsource2.png" /></div></center>
<center><div class="eq"><img alt="" src="eqsource3.png" /></div></center>
<center><div class="eq"><img alt="" src="eqsource4.png" /></div></center>

<p />
There exists general purpose solvers for these kind of problems that
are very fast and can literally handle millions of variables. To use
them however the problem has to be transformed into some specific
matrix form, and the coefficients of all the matrices
has to be passed to the solver using some API. This transformation is
a tedious and error prone step that forces you to work with matrix
indexes instead of readable variable names. Also it makes maintaining
an implementation hard since any modification has to be transformed
too.

<p />
The example above comes from the manual of
the <a href="ftp://ftp.gnu.org/pub/gnu/glpk/">glpk</a> library. That
manual continues by describing how to convert this problem into the
standard form of glpk (which involves introducing three new variables)
and then gives the <a href="sample.c">c-code</a> needed to call the
library. Relating that c-code to the problem above without the
intermediate explanation of the manual is not easy. A common
solution here is to build a hi-level interface that allows a more
natural way of defining the matrices and/or allow the equations to be
entered symbolically. Unfortunately, such interfaces often become
slow. For the benchmark below for example, 
<a href="http://abel.ee.ucla.edu/cvxopt">cvxopt</a>
requires 20 minutes to setup a problem that takes 9.43 seconds to solve
(this seems a bit extreme, am I doing something wrong?).

<p />
The high-level interface I constructed on top of the
<a href="ftp://ftp.gnu.org/pub/gnu/glpk/">glpk</a> library is 
<a href="https://bitbucket.org/hakanardo/pplp">pplp</a> and it allows
the equations to be entered symbolically. The above problem can be
solved using
<pre>
    lp = LinearProgram()
    x, y, z = lp.IntVar(), lp.IntVar(), lp.IntVar()
    lp.objective = 10*x + 6*y + 4*z
    lp.add_constraint( x + y + z &lt;= 100 )
    lp.add_constraint( 10*x + 4*y + 5*z &lt;= 600 )
    lp.add_constraint( 2*x + 2*y + 6*z &lt;= 300 )
    lp.add_constraint( x &gt;= 0 )
    lp.add_constraint( y &gt;= 0 )
    lp.add_constraint( z &gt;= 0 )

    maxval = lp.maximize()
    print maxval
    print x.value, y.value, z.value
</pre>

<p />
To benchmark the API I used it to solve a 
<a href="http://en.wikipedia.org/wiki/Minimum-cost_flow_problem">minimum-cost
  flow problem</a> with 154072 nodes and 390334 arcs. The C library
  needs 9.43 s to solve this and the pplp interface adds another 5.89
  s under PyPy and 28.17 s under CPython. A large amount of time is
  still spend setting up the problem, but it's a significant
  improvement over the 20 minutes required on CPython by
  <a href="http://abel.ee.ucla.edu/cvxopt">cvxopt</a>. It is
  probably not designed to be fast on this kind of benchmark. I have
  not been able to get cvxopt to work under PyPy. The benchmark used is
  available <a href="https://bitbucket.org/hakanardo/pplp/src/default/benchmark/">here</a>
  


</body>
</html>
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.