6 ms·

Linear Programming in Python (2023)

53 points by bwestergard 3y ago

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.
vonnik 3y ago
Fwiw, reinforcement learning offers objectively better optimization and more efficient inference than LP in many cases.
- ashish01 3y ago
  Any good examples or notebooks using RL to solve typical optimization problems?
  - bshipp 3y ago
    I also am curious about this statement. If a problem becomes too complex for linear programming solutions, how easy is it to know that a reinforcement learning solution is actually a global optima and not just local?
    - ke88y 3y ago
      > how easy is it to know that a reinforcement learning solution is actually a global optima and not just local? If the problem is too complex for LP then you're probably not going to get a global optimal from RL either.
      - bshipp 3y ago
        Fair enough. I'm not invested in LP or RL, but my background is in agriculture and LP forms the basis of a lot of cropping/feeding decision trees. I'd be curious to explore new techniques, but it sounds like the discussion here is for a different set of linear programming problems than the ones I see most often, and that there's likely a limited upside toward implementing RL.
        ke88y 3y ago
        If you have a working LP solution without any glaring compromises in the problem formulation, then I'm not sure why one would want to throw out a perfectly good working solution... algorithms are the means, not the ends :)
xiaoxiae 3y ago
Author here (and a long time HN lurker), really cool to see someone post this here :). As mentioned at the beginning, the article was created mostly as additional resources for my video about LP (https://www.youtube.com/watch?v=E72DWgKP_1Y https://www.youtube.com/watch?v=E72DWgKP_1Y), which I think is definitely worth a watch if you find this interesting!
- bwestergard 3y ago
  Your video is really excellent. I've subscribed to your channel and hope you produce more. Any way we can support your work?
  - xiaoxiae 3y ago
    Thank you for the kind words, I am happy that you liked it :)! The best way to support my work is through Patreon: https://www.patreon.com/YTomS https://www.patreon.com/YTomS.
- jmholla 3y ago
  Two things I noticed: * The first problem is rather trivial problem. That may be the point, but I haven't watched the video to know for sure. * The font used for source code is making <= display as ≤ on my browser.
  - xiaoxiae 3y ago
    * That is intended, the video is an introduction to LP. * I use Fira Code, which makes certain symbol combinations as ligatures. Looking at it now, this is pretty awful to use on a website and confuses peolpe, I'll disable them.
adammarples 3y ago
cvxpy is imo the best package for this in python
- tnecniv 3y ago
  I agree I just wish the docs were better. Maybe they’ve improved since I used it last but I remember having to hunt for whatever the equivalent of a certain numpy function was and it wasn’t the easiest to find
  - sdiamond9 3y ago
    cvxpy dev here. We have an intern project to improve the docs, in particular making the list of functions easier to navigate/search. Agreed there is room for improvement right now...
JZL003 3y ago
It's worth looking at julia's JuMP, I find it very ergonomic, fast, and easy to try differnet LP solvers Also https://neos-server.org/neos/solvers/index.html https://neos-server.org/neos/solvers/index.html is an amazing resource I don't see used often. These solvers are very expensive and it's not obvious which solver will solve a given problem fastest (if it supports the problem's type) because it depends on which heuristics they use. So you can submit example (medium-sized) problems here, try out a bunch, and get your company/buy the one which you know works best

53 points by bwestergard 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.

vonnik 3y ago

Fwiw, reinforcement learning offers objectively better optimization and more efficient inference than LP in many cases.

ashish01 3y ago
Any good examples or notebooks using RL to solve typical optimization problems?
- bshipp 3y ago
  I also am curious about this statement. If a problem becomes too complex for linear programming solutions, how easy is it to know that a reinforcement learning solution is actually a global optima and not just local?
  - ke88y 3y ago
    > how easy is it to know that a reinforcement learning solution is actually a global optima and not just local? If the problem is too complex for LP then you're probably not going to get a global optimal from RL either.
    - bshipp 3y ago
      Fair enough. I'm not invested in LP or RL, but my background is in agriculture and LP forms the basis of a lot of cropping/feeding decision trees. I'd be curious to explore new techniques, but it sounds like the discussion here is for a different set of linear programming problems than the ones I see most often, and that there's likely a limited upside toward implementing RL.
      - ke88y 3y ago
        If you have a working LP solution without any glaring compromises in the problem formulation, then I'm not sure why one would want to throw out a perfectly good working solution... algorithms are the means, not the ends :)

xiaoxiae 3y ago

Author here (and a long time HN lurker), really cool to see someone post this here :). As mentioned at the beginning, the article was created mostly as additional resources for my video about LP (https://www.youtube.com/watch?v=E72DWgKP_1Y https://www.youtube.com/watch?v=E72DWgKP_1Y), which I think is definitely worth a watch if you find this interesting!

bwestergard 3y ago
Your video is really excellent. I've subscribed to your channel and hope you produce more. Any way we can support your work?
- xiaoxiae 3y ago
  Thank you for the kind words, I am happy that you liked it :)! The best way to support my work is through Patreon: https://www.patreon.com/YTomS https://www.patreon.com/YTomS.
jmholla 3y ago
Two things I noticed: * The first problem is rather trivial problem. That may be the point, but I haven't watched the video to know for sure. * The font used for source code is making <= display as ≤ on my browser.
- xiaoxiae 3y ago
  * That is intended, the video is an introduction to LP. * I use Fira Code, which makes certain symbol combinations as ligatures. Looking at it now, this is pretty awful to use on a website and confuses peolpe, I'll disable them.

adammarples 3y ago

cvxpy is imo the best package for this in python

tnecniv 3y ago
I agree I just wish the docs were better. Maybe they’ve improved since I used it last but I remember having to hunt for whatever the equivalent of a certain numpy function was and it wasn’t the easiest to find
- sdiamond9 3y ago
  cvxpy dev here. We have an intern project to improve the docs, in particular making the list of functions easier to navigate/search. Agreed there is room for improvement right now...

JZL003 3y ago

It's worth looking at julia's JuMP, I find it very ergonomic, fast, and easy to try differnet LP solvers Also https://neos-server.org/neos/solvers/index.html https://neos-server.org/neos/solvers/index.html is an amazing resource I don't see used often. These solvers are very expensive and it's not obvious which solver will solve a given problem fastest (if it supports the problem's type) because it depends on which heuristics they use. So you can submit example (medium-sized) problems here, try out a bunch, and get your company/buy the one which you know works best