Linear Programming in Python (2023)

https://slama.dev/youtube/linear-programming-in-python/

by bwestergard • 3 years ago

53 53 3 years ago

ant6n3• 3 years 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• 3 years ago

There is also 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• 3 years 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

notatallshaw2• 3 years 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

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?

ant6n3• 3 years 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.

ashish012• 3 years 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) or Python's Z3 interface, depending on the problem I'm working on.

vonnik3• 3 years ago

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

ashish012• 3 years ago

Any good examples or notebooks using RL to solve typical optimization problems?

bshipp4• 3 years 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?

ke88y4• 3 years ago

The cons are that RL sometimes requires more babysitting, more non-subject-matter (ie, optimization-method-specific) expertise, and can be a bit less... predictable... at inference time.

Also, LP often offers perfectly acceptable optimization and latency. The only case where this isn't true for offline problems is where LP times out or where relaxations of the problem are required to prevent timeout.

If I had to choose one method to learn, I guess I would learn RL. But it's a false choice. Given that I know both well, I'd reach for LP unless there was a good reason to use RL instead. And from a user perspective LP is much easier to learn than RL (see cons), so I think this is good general advice. Definitely worth having both tools on your belt if you plan on working on problems where either is a good fit.

taeric7• 3 years ago

I would think you'd pick LP if your problem's decision space is modeled in a way that is compatible with it. And if all you have is effectively a simulator and a cost function, then RL is the way to go?

bwestergard2• 3 years ago

"reinforcement learning offers objectively better optimization"

I don't follow. Linear programming (with the simplex method) finds the optimal solution set for any linear program eventually. How can reinforcement learning be "better" apart from efficiency?

choeger• 3 years ago

It can't. They're talking out of their backend.

ashley93• 3 years ago

This is such a sweeping generalization with no context whatsoever, that it's really hard to say anything about this.

They're two different methodologies that are most of the time applied to vastly different problems.

PartiallyTyped• 3 years ago

Citation needed.

RL makes sense when you don’t know the dynamics of the environment and have interactions with it.

Linear programming can be done when you can encode a problem as linear constraints which means you know the dynamics. You can then find the optimal set of points of the convex polyhedron defined by the constraints via interior point methods.

That’s it. You don’t need exploration and you can get an optimal solution to the constraints because the feasible space is convex.

whatever15• 3 years ago

Not only you provide no evidence, but also your statements are flat out wrong.

Not even the founding fathers of RL (Bertsekas et al) have made such claims.

RL almost always solves an approximation of the dynamic program. Aka no guarantees of consistent optimality.

RL does not guarantee constraint satisfaction.

RL needs tons of data to learn the state space and still is not enough. LPs solve nowadays Traveling salesman problems to optimality with millions of nodes. RL close to optimality for less than 1000 nodes.

graycat6• 3 years ago

I studied LP (linear programming) from some of the most advanced researchers in optimization, including LP, in the world, led the class in a Ph.D. qualifying exam mostly on LP, wrote a Ph.D. dissertation in optimization, taught linear programing in college and graduate school, and applied it in business.

From that background, given a problem in LP, there are three cases, the problem is (1) infeasible, (2) feasible and bounded, and (3) feasible and unbounded.

In case (2), at least one of the extreme points (intuitively, a sharp point) of the set of feasible points is optimal. For an algorithm, the famous simplex algorithm will find an optimal extreme point in finitely many iterations in finite time. For the computing, about all that can go wrong is from a problem being too big or causing poor numerical accuracy.

Thus, given an LP, the claim

"objectively better optimization",

that there was any "optimization" at all means that the problem is in case (2), feasible and bounded. Then claim

"objectively better optimization"

is essentially not possible.

taeric7• 3 years ago

Your response makes me wonder if the idea is not that RL can give more optimal solutions, but perhaps more robust ones?

This is giving a ton of charity to the opening post, but fun for me to consider. As you say, given a model, if it is bounded than LP is an obvious route to get optimal. However, models being what they are, there are often times when the prescribed solution is unrealizable for reasons. Reinforcement learning being what it is, is an interesting way to add new features to a model that can "cost in" the penalties that come from non-realized optimal solutions.

That make sense? I'm assuming this has been studied, and I simply don't know the names to look into.

xiaoxiae3• 3 years 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), which I think is definitely worth a watch if you find this interesting!

bwestergard2• 3 years ago

Your video is really excellent. I've subscribed to your channel and hope you produce more. Any way we can support your work?

xiaoxiae3• 3 years 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.

jmholla• 3 years 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.

xiaoxiae3• 3 years 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• 3 years ago

cvxpy is imo the best package for this in python

tnecniv2• 3 years 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• 3 years 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• 3 years 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 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

Linear Programming in Python (2023)

Related Stories