Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linear Programming in Python (2023)

slama.dev

Post reply on HN
Print view View original

21–30 of 56 posts

Re: Linear Programming in Python (2023)

#21

Post by graycat »

vonnik wrote: post #5

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

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.

Re: Linear Programming in Python (2023)

#22

Post by xiaoxiae »

bwestergard wrote: post #18
xiaoxiae wrote: post #12

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!

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

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.

Re: Linear Programming in Python (2023)

#23

Post by ke88y »

bshipp wrote: post #16
ke88y wrote: post #14

Earlier quoted context omitted.

> 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.

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.

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 :)

Re: Linear Programming in Python (2023)

#24

Post by tnecniv »

bshipp wrote: post #9
ashish01 wrote: post #7

Earlier quoted context omitted.

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

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?

While I disagree with the RL assertion without a source, linear programs are convex, so local optima are global optima.

However, unless there is some aspect of the problem which is not known (e.g., you don’t exactly know the objective or constraints), so you model it as a distribution over LPs, I really don’t know how RL will help you. Gradient-based methods can give you improvements if your problem is very large scale and doesn’t have, e.g., sparse structure, but the above claim is bold.

Re: Linear Programming in Python (2023)

#25

Post by tnecniv »

adammarples wrote: post #13

cvxpy is imo the best package for this in python

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

Re: Linear Programming in Python (2023)

#26

Post by taeric »

graycat wrote: post #21
vonnik wrote: post #5

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

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 an…

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.

Re: Linear Programming in Python (2023)

#27

Post by sdiamond9 »

tnecniv wrote: post #25
adammarples wrote: post #13

cvxpy is imo the best package for this in python

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

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...

Re: Linear Programming in Python (2023)

#28

Post by taeric »

ke88y wrote: post #8
vonnik wrote: post #5

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

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 choo…

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?

Re: Linear Programming in Python (2023)

#29

Post by whatever1 »

taeric wrote: post #26
graycat wrote: post #21

Earlier quoted context omitted.

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 an…

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…

If you need robustness you can explicitly model an uncertainty set for your problem coefficients, and solve to optimality the robust optimization problem. That way you know exactly your degree of “insurance” to uncertainty. You also know that this is the absolute best you can do in view of this uncertainty set.

Re: Linear Programming in Python (2023)

#30

Post by taeric »

whatever1 wrote: post #29
taeric wrote: post #26

Earlier quoted context omitted.

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…

If you need robustness you can explicitly model an uncertainty set for your problem coefficients, and solve to optimality the robust optimization problem. That way you know exactly your degree of “insurance” to uncertainty. You also know that this is the absolute best you can do in view of this uncertainty set.

Right, I am asking if RL may be a somewhat easy way to get that in there? Since a lot of robustness is best known after a series of losses.

That is, if you know what your total exposure to risk is, then LP is still ultimately the answer. If you don't, you need some way to monte carlo different scenarios to get an idea. And at that point, I feel you have backed yourself into RL?

Post reply on HN