Live data from Hacker News

Linear Programming in Python (2023)

slama.dev

51–56 of 56 posts

Re: Linear Programming in Python (2023)

#51
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?

Small point: If you want to do Monte Carlo on an LP (linear program), then using the simplex algorithm, for the first Monte Carlo trial, go ahead and find the optimal solution. Then for the rest of the trials, start with the optimal solution, the basic variables, and the matrix inverse of the basis matrix and from those find the next optimal solution -- that solution will nearly always come quite quickly. So, you will be able to have a good collection of Monte Carlo trials for surprisingly little more computing than for the first optimal solution.

Re: Linear Programming in Python (2023)

#52
post #51
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?

Small point: If you want to do Monte Carlo on an LP (linear program), then using the simplex algorithm, for the first Monte Carlo trial , go ahead and find the optimal solution. Then for the rest of the trials, start with the optimal solution, the basic variables, and the matrix inverse of the basis matrix and from those find the next optimal solution -- that solution will nearly always come quite quickly. So, you wi…

I knew you can carry forward solutions in most solvers. I'd assume you would be changing constraints some, though I imagine most constraints would not be changed such that a lot of the discovered solution would still be good?

Re: Linear Programming in Python (2023)

#53
post #47
post #46

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? LP (linear programming), given an optimal solution, has some sensitivity analysis that nicely addresses robustness . In the LP find x to solve maximize z = cx subject to Ax = b, x >= 0, small changes in c, A, and b can result in large changes in x (below I explain some of how). But, still, due to…

Ish? Sensitivity analysis measures, by definition, sensitivity to inputs. I suppose you can model it so that some extrinsic factors are themselves written as inputs, but I haven't seen this explored with the idea of robustness, much. (Granted I may just be ignorant in that area.) What you are pointing to, seems to be degrees of freedom on an input? The more options you have in an input, the better. Robust systems als…

> common in LP formulations?

If you want to consider the effects of war, inflation, something like the 2008 housing crash, economic depression, COVID, hurricanes, train derailments, etc., sure, if those hypothetical changes still yield an LP (linear program), can just solve the resulting LPs and display the resulting data in a way can visualize and get some intuitive insight.

But there is another way: Let insurance companies consider history and set insurance premiums for disasters, all disasters, ever seen before or not, and they will have quite good data, likely, sorry, better than get from RL (reinforcement learning) or, really, anything that can be obtained from anything like current analysis of data from Web crawling. A common assumption, understanding in business is that it is possible to get insurance on nearly anything against nearly anything. E.g., the whole thing about the book and movie The Big Short was that it was possible to get insurance on the BBB tranches of housing mortgage bonds, make a bet that the tranches would fail. For this would have to pay monthly premiums but when the tranches failed make huge returns on the premiums paid.

With their good data and history, an insurance company will be able to set insurance premiums that give you some good information about the seriousness of the disasters, on your list of disasters or not, you are concerned about. If seeing the premiums you are still highly concerned, then pay the premiums and relax.

As in The Big Short, call up Goldman-Sachs and see if they will write you some insurance on what you want protected.

Sure, if I were to invest, what for me are big bucks, in raising a flock of chickens, maybe I'd get some insurance against any disease, e.g., bird flu, attacks by rabid foxes, wolves, raccoons, fire, flood, tornado, etc. destroying the flock.

Sure, once I did some Monte Carlo work essentially to evaluate the odds of some survivors in a really complex, goofy situation -- with those odds, could have found premiums for writing insurance policies. The issue was, if there were global nuclear war limited to sea, how long would the US SSBN fleet survive? For input, I used some encounter rate probability derivations Koopman did as part of ocean search in WWII. Then I used some detection radii of Red-Blue pairs and battle result probabilities (one dies, the other dies, both die, neither dies). My work passed technical review by a world-class probability professor. My summary results were a graph over time of the expected number of SSBNs surviving. Also the Monte Carlo result could have also reported the probabilities of other aspects of the scenario, e.g., the probability that at least 10 survived for 30 days, enough to write an insurance policy!

The professor tried to object: He said how could I hope to "fathom" the huge state space? I responded, ..., using the strong law of large numbers ..., and he agreed with me. So, sometimes can analyze situations where some of the possibilities, actually nearly all, are never encountered or sampled. So, that would beat running LP many times one at a time on many disasters could describe.

Lesson: Sometimes it's possible to do Monte Carlo under some seemingly wildly complicated situations.

Net, I would advise pricing some insurance instead of some DIY (do it yourself) with either LP or RL.

More broadly and by analogy, a hammer and a screwdriver are both good tools, but no sense in asking which is better. Maybe the same for LP and RL. And for one more tool, insurance policies.

Re: Linear Programming in Python (2023)

#54
post #52
post #51

Earlier quoted context omitted.

Small point: If you want to do Monte Carlo on an LP (linear program), then using the simplex algorithm, for the first Monte Carlo trial , go ahead and find the optimal solution. Then for the rest of the trials, start with the optimal solution, the basic variables, and the matrix inverse of the basis matrix and from those find the next optimal solution -- that solution will nearly always come quite quickly. So, you wi…

I knew you can carry forward solutions in most solvers. I'd assume you would be changing constraints some, though I imagine most constraints would not be changed such that a lot of the discovered solution would still be good?

The change that would make finding the next solution maybe not quickly would be to the basis matrix and its inverse from the last solution. Still, finding a new basis inverse would be much faster than starting from just the whole problem. Yes, changes in the basis matrix could make that basis infeasible, but could attack that the usual way with artificial variables, and there may be still better ways.

Changes in the costs c, the right hand side b, or the non-basic columns of matrix A would let the new solution be found usually quickly.

Re: Linear Programming in Python (2023)

#55
post #48

Earlier quoted context omitted.

Our work was precisely in optimization over massive numbers of possible scenarios amid multi-dimensional uncertainties. Again, significantly outperforms LP. Not surprised that you are an advocate of math optimization. Most people working on optimization in industrial operations and supply chains have an OR background, and this sort of conservatism is common. But there are lots of situations that LP can't optimize whi…

"Again, significantly outperforms LP." No, this is mathematically impossible. You cannot out-optimize a mathematical global optimization solver. Whether that is LP, MILP, or NLP. Exactly because they provide a certificate of optimality. It is like stating that you found a non-negative number that is smaller than 0. It’s not progressive. It’s flat out wrong. "But there are lots of situations that LP can't optimize whi…

[deleted]

Re: Linear Programming in Python (2023)

#56
post #38

Earlier quoted context omitted.

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.

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?

Post reply on HN