Live data from Hacker News

Linear Programming in Python (2023)

slama.dev

31–40 of 56 posts

Re: Linear Programming in Python (2023)

#31
post #30

Earlier quoted context omitted.

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?

Fair point, but there are no shortcuts. Either you will use domain knowledge and you will build a model-based approach (LP, IP, MINLP, CP/SAT, DP), or you will have to find terabytes of good quality samples to feed the RL beast, hoping it will approximate a good enough policy / value function.

The main appeal of RL is for cases where an explicit model cannot be derived. Think of very complex chemical reactions or other system dynamics. There indeed, you can go with RL and cross your fingers.

If your process is dangerous, we must also have a supervisor system, to ensure that the RL actions will not lead to catastrophic situations (from violating constraints). Like Teslas targeting firetrucks.

Re: Linear Programming in Python (2023)

#32
post #30

Earlier quoted context omitted.

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?

Fair point, but there are no shortcuts. Either you will use domain knowledge and you will build a model-based approach (LP, IP, MINLP, CP/SAT, DP), or you will have to find terabytes of good quality samples to feed the RL beast, hoping it will approximate a good enough policy / value function. The main appeal of RL is for cases where an explicit model cannot be derived. Think of very complex chemical reactions or oth…

Absolutely! I said in another post that I assumed you'd use LP if your decision space was modeled in such a way that that can work, but RL if you instead have more of a simulator and a cost function. Even that, I grant, is over simplified.

Mainly trying to find a way to use charity for that opening post. At face value, I don't know what they were getting at.

Re: Linear Programming in Python (2023)

#33

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!

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.

Re: Linear Programming in Python (2023)

#34
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

Re: Linear Programming in Python (2023)

#35
post #26
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…

A linear programming (LP) problem is essentially just, for positive integers m and n and real or rational matrices

1 by n c

n by 1 x

m by n A

m by 1 b

1 by 1 z,

maximize z = cx

subject to Ax = b, x >= 0

That is, an LP is a fully precisely stated problem in math. There is no randomness, ambiguity, flexibility, uncertainty, etc.

Now when move to the real world and have a problem, e.g., in mixing animal feed, cracking crude oil, we have some real world considerations that are not really LP. But in some cases, maybe it appears, after some examination, that we can take the real problem and formulate it as an LP. The formulation may have some of these real considerations, but once we have our LP, all we can hope to get from the LP is the usual LP results -- an optimal solution, maybe infinitely many alternate optima (other solutions also optimal), some sensitivity analysis on how much we could change some of the input data and have the solution we found remain optimal, and some more, but none of this goes very far on resolving the real world issues of randomness, etc.

So, sure, maybe we (1) several times adjust the input data and solve the LP again, (2) move to non-linear programming (quadratic programming, the Kuhn-Tucker conditions, etc.) or integer linear programming, or (3) have some models of the randomness and move to optimization under uncertainty, e.g., stochastic dynamic programming.

Main point: There is (A) the math and (B) the real world, and the two are not the same. Hopefully the real world problem can be solved nicely with some math, but we should know when we jump from the (a) real problem to the (b) math problem and have good understandings of the relevant issues of both (a) and (b).

For a (crude) analogy, the math, e.g., LP is just a tool. E.g., recently somehow my plastic mail box got whacked with some cracked plastic and a hole in the top. Fixes used some tools, tape measure, hand saw, bridge saw, circle saw, hand planer, wire brush, electric drill, epoxy glue, spray paint, ... -- but none of these were directly "mailbox fixes" but just tools useful in fixing the mailbox. In this analogy, the math is not a real fix but just some tools that might yield a real fix.

Re: Linear Programming in Python (2023)

#36
post #24
post #9

Earlier quoted context omitted.

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

That's an excellent point. I think one complex agriculture issue I've encountered that LP would struggle to handle is something like inventory control of perishable goods, where there's variance in incoming quality, degradation during storage, and variance in shelf-life based on age of crop, growing conditions, etc. LP would work great for handling grain storage, where a crop generally maintains a known quality profile over time with limited shrinkage, but I could see a use for a machine learning algorithm that handles perishable goods stochastic variables in a more direct way.

Re: Linear Programming in Python (2023)

#37
post #23
post #16

Earlier quoted context omitted.

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

I'm pretty sure the main reason for throwing out old tools that still function in favor of the new hotness is developer boredom.

Re: Linear Programming in Python (2023)

#38
post #2

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.

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

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.

Re: Linear Programming in Python (2023)

#39
post #33

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!

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.

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

Re: Linear Programming in Python (2023)

#40
post #19

Earlier quoted context omitted.

"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?

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

>Founder of Pathmind/Skymind (W16) - Pathmind: Deep reinforcement learning to optimize supply chain and scheduling

actually i guess they're shilling - not that there's that much of a differnce.

Post reply on HN