PuLP very slow when adding many constraints

Question

I'm trying to use PuLP, but it is taking 50 seconds to add 4000 constraints (with 67 variables). Solving the problem only takes a fraction of a second.

We want to use PuLP to easily test several solvers on a large set of problems.

Should it be taking PuLP this long? Using PyGLPK directly takes only a fraction of second including both setup and solving, so I hope not. What can I do to improve the efficiency of this step in PuLP?

---

Update

My constraints matrix is very sparse, and I was able to reduce the setup time to 4 or 5 seconds for this particular problem by only including nonzero coefficients. I am still able to write my own .lp or .mps formatted file, solve the problem with a cbc or glpsol subprocess, and parse the solution much more efficiently than PuLP, simply because I can write the input file in a few ms when PuLP takes several seconds. I'm still not sure why this would be.

Answer 1

I don't have reps enough to comment.

But have you looked at this:

https://groups.google.com/forum/#!topic/pulp-or-discuss/p1N2fkVtYyM

The question is asked:

"The problem is solved in less than 0.5 second.
However setting it up with PULP takes more than 10 seconds. "

This seems to be what you report as well. And the solution is to not use += or sum(...) operators, but instead, as explained in the link as well:

yeah using the += operator with pulp is really slow, as is using sum() 
instead of lpSum()

So maybe you are adding the constraints 1 at a time to PuLP instead of building the list of constraints first and then, at the end, add the constraints to PuLP?

Answer 2

I had a similar problem, with a expression with > 10,000 variables that I was using for my objective function. The root cause was the same as the original poster saw. Using sum on an array of pulp.LpVariable is really slow compared to pulp.LpAffineExpression. Based on the Google Groups discussion in the accepted answer I was able make my code go much faster. I know this is an old questions, but will includes some abstracted code for the impatient.

The original objective looked like:

sum([x * k for x in xs] + ys)

where xs is a list of pulp.LpVariable, k is a floating point constant, and ys is another list of pulp.LpVariable.

A much faster version is:

pulp.LpAffineExpression([(x, k) for x in xs] + [(y, 1.0) for y in ys])

I did not precisely time either version. To give an idea of the time difference, while running the slow version, I was able to search the Internet for why pulp might be so slow, find this StackOverflow question, read the linked discussion, and update my code before the expression was done evaluating. The second version takes a few seconds.