3 ms·

I have often started modeling problems with pulp. As the problem size gets bigger, pulp will fail to work —- that is, pulp handles writing out large problems to

by ant6n 3y ago

I have often started modeling problems with pulp. As the problem size gets bigger, pulp will fail to work —- that is, pulp handles writing out large problems to disk (nlogn complexity) worse than gurobi handles reading and solving them (expn complexity). Then I end up writing out the problems into text files on python „by hand“, which is very cumbersome. I wish python and it’s libraries wasn’t so inefficient.

unnah 3y ago
There is also https://www.python-mip.com/ https://www.python-mip.com/ which claims to be more efficient, but it supports fewer solvers than pulp, and I have not had opportunity to test it. Would anyone here have experience on how well their efficiency claims hold in practice?
- mulmboy 3y ago
  I've used python-mip extensively, though only on problems with up to ~10k variables, and only using basic LP features (no advanced solver callbacks). python-mip is substantially faster than cvxpy, pulp, and pyomo for constructing _and solving_ a very simple LP with 10k variables. It's on par even with cylp using vectorisation (maybe I haven't used cylp as well as I could (either way cylp is dreadful to use)). I say _and solving_ because for my use case it's the time to construct and solve relatively simple & small problems (like, <100ms overall) that I'm interested in, which includes anything like serialising the problem to a file and invoking the solver. But keep in mind these kinds of benchmarks can depend a lot on how you're using the library. Like, are you spending almost all time actually solving the model? Then it probably doesn't matter what library you use to construct the model. python-mip in general is pretty nice. It supports advanced solver features if you're into that sorta stuff. But their typing is a bit whacky (no py.typed file, use numbers.Real for typing which makes type checking a bit whacky). And it relies on a funky pre-compiled CBC binary (I had to compile it from scratch at a very specific commit to get it working on M1). python-mip creates/modifies variables in the underlying solver library (CBC/Gurobi) as you create/modify variables through the python interface (I believe this is an uncommon approach, but good). The internal data model of variables & linear expressions is quite clean and tidy. Overall would recommend python-mip if you just need to solve MILP problems. From my scrappy benchmark constructing and solving a very simple LP with 10k variables: 'benchmark_python_mip' took: 40.33 ms 'benchmark_cvxpy' took: 738.11 ms 'benchmark_pulp' took: 152.68 ms 'benchmark_pyomo' took: 191.66 ms 'benchmark_cylp' took: 38.91 ms
  - ant6n 3y ago
    I tend to build mip problems that take days to make a good approximation (using gurobi). Those can not be modeled using pulp, because I run out of memory. I’ll check out python-mip, thanks for the tip.
notatallshaw 3y ago
Taking a look at pulp it just seems to be a solver abstraction API and all the real work is done by solver libraries written in lower-level languages. It looks like the default solver is COIN-OR CLP/CBC, and that's written in C++: https://github.com/coin-or/Cbc/tree/master/src https://github.com/coin-or/Cbc/tree/master/src Maybe I'm misunderstanding something here and it's the abstraction API causing the problems, but it seems like it's up to the solver implementation to be efficient here?
- ant6n 3y ago
  The point is that the solvers can deal with larger problems than pulp. gurobi can deal with hundreds of thousands of expressions, but then pulp will just run out of memory at that point.
  - notatallshaw 3y ago
    Well I was replying to this: > I wish python and it’s libraries wasn’t so inefficient. And it seems like Pulp isn't a solver by itself so comparing it to gurobi doesn't make a lot of sense? I see gurobi also has a Python interface, so comparing it to that makes more sense. Does the gurobi Python interface run out of memory? I suppose it matters what part of Pulp is running out of memory, the underlying solver being used or is the API itself taking up the memory?
ashish01 3y ago
PuLP is a great way to get started, and I used it as my first attempt for many problems. However, I have since switched to using Google OR tools (https://developers.google.com/optimization/pack/bin_packing https://developers.google.com/optimization/pack/bin_packing) or Python's Z3 interface, depending on the problem I'm working on.

by ant6n 3y ago

unnah 3y ago

There is also https://www.python-mip.com/ https://www.python-mip.com/ which claims to be more efficient, but it supports fewer solvers than pulp, and I have not had opportunity to test it. Would anyone here have experience on how well their efficiency claims hold in practice?

mulmboy 3y ago
I've used python-mip extensively, though only on problems with up to ~10k variables, and only using basic LP features (no advanced solver callbacks). python-mip is substantially faster than cvxpy, pulp, and pyomo for constructing _and solving_ a very simple LP with 10k variables. It's on par even with cylp using vectorisation (maybe I haven't used cylp as well as I could (either way cylp is dreadful to use)). I say _and solving_ because for my use case it's the time to construct and solve relatively simple & small problems (like, <100ms overall) that I'm interested in, which includes anything like serialising the problem to a file and invoking the solver. But keep in mind these kinds of benchmarks can depend a lot on how you're using the library. Like, are you spending almost all time actually solving the model? Then it probably doesn't matter what library you use to construct the model. python-mip in general is pretty nice. It supports advanced solver features if you're into that sorta stuff. But their typing is a bit whacky (no py.typed file, use numbers.Real for typing which makes type checking a bit whacky). And it relies on a funky pre-compiled CBC binary (I had to compile it from scratch at a very specific commit to get it working on M1). python-mip creates/modifies variables in the underlying solver library (CBC/Gurobi) as you create/modify variables through the python interface (I believe this is an uncommon approach, but good). The internal data model of variables & linear expressions is quite clean and tidy. Overall would recommend python-mip if you just need to solve MILP problems. From my scrappy benchmark constructing and solving a very simple LP with 10k variables: 'benchmark_python_mip' took: 40.33 ms 'benchmark_cvxpy' took: 738.11 ms 'benchmark_pulp' took: 152.68 ms 'benchmark_pyomo' took: 191.66 ms 'benchmark_cylp' took: 38.91 ms
- ant6n 3y ago
  I tend to build mip problems that take days to make a good approximation (using gurobi). Those can not be modeled using pulp, because I run out of memory. I’ll check out python-mip, thanks for the tip.

notatallshaw 3y ago

Taking a look at pulp it just seems to be a solver abstraction API and all the real work is done by solver libraries written in lower-level languages. It looks like the default solver is COIN-OR CLP/CBC, and that's written in C++: https://github.com/coin-or/Cbc/tree/master/src https://github.com/coin-or/Cbc/tree/master/src Maybe I'm misunderstanding something here and it's the abstraction API causing the problems, but it seems like it's up to the solver implementation to be efficient here?

ant6n 3y ago
The point is that the solvers can deal with larger problems than pulp. gurobi can deal with hundreds of thousands of expressions, but then pulp will just run out of memory at that point.
- notatallshaw 3y ago
  Well I was replying to this: > I wish python and it’s libraries wasn’t so inefficient. And it seems like Pulp isn't a solver by itself so comparing it to gurobi doesn't make a lot of sense? I see gurobi also has a Python interface, so comparing it to that makes more sense. Does the gurobi Python interface run out of memory? I suppose it matters what part of Pulp is running out of memory, the underlying solver being used or is the API itself taking up the memory?

ashish01 3y ago

PuLP is a great way to get started, and I used it as my first attempt for many problems. However, I have since switched to using Google OR tools (https://developers.google.com/optimization/pack/bin_packing https://developers.google.com/optimization/pack/bin_packing) or Python's Z3 interface, depending on the problem I'm working on.