Linear Programming in Python (2023)(slama.dev)
slama.dev
Linear Programming in Python (2023)
https://slama.dev/youtube/linear-programming-in-python/
55 comments
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.
The best way to support my work is through Patreon: https://www.patreon.com/YTomS.
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.
* 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.
* 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.
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
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
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.
I wish python and it’s libraries wasn’t so inefficient.
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?
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
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
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.
I’ll check out python-mip, thanks for the tip.
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?
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?
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?
> 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?
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.
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...
Fwiw, reinforcement learning offers objectively better optimization and more efficient inference than LP in many cases.
"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?
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.
Speaking from years of experience comparing RL results to those of LP done with tools like Gurobi on industrial operations and supply chain optimization problems while at my former startup, which was acquired two years ago, so I am not shilling anything.
There are many problems that are hard to represent such that LP can compute them. That process alone is long, and hard to adjust even though clients need to make those adjustments.
These problems include multi-echelon inventory optimizations, and load-balancing across multiple assembly lines in factories when using hundreds of delivery vehicles, among others. These are properly multi-agent problems that RL solves well if given a valid simulation of the environment. LP often cannot solve it at all.
In cases where we went head to head with well known LP software vendors, we were able to move the Pareto frontier by double digit percentages.
We open sourced our software here after the acquihire. Depends on Gym among other repositories. Does something similar to Microsoft’s Bonsai. All are welcome to use.
https://github.com/PathmindAI
There are many problems that are hard to represent such that LP can compute them. That process alone is long, and hard to adjust even though clients need to make those adjustments.
These problems include multi-echelon inventory optimizations, and load-balancing across multiple assembly lines in factories when using hundreds of delivery vehicles, among others. These are properly multi-agent problems that RL solves well if given a valid simulation of the environment. LP often cannot solve it at all.
In cases where we went head to head with well known LP software vendors, we were able to move the Pareto frontier by double digit percentages.
We open sourced our software here after the acquihire. Depends on Gym among other repositories. Does something similar to Microsoft’s Bonsai. All are welcome to use.
https://github.com/PathmindAI
In operations and supply chains it is not hard to find *A* solution. Operators literally make these decisions manually every day without the need for any computer.
The main challenge is to optimize these decisions. With optimality guarantees. Consistently. Day in, day out, with various uncertainties.
That is what math optimization has been doing for decades.
And no, RL is nowhere to be seen in production, except from some consulting projects that are abandoned.
The main challenge is to optimize these decisions. With optimality guarantees. Consistently. Day in, day out, with various uncertainties.
That is what math optimization has been doing for decades.
And no, RL is nowhere to be seen in production, except from some consulting projects that are abandoned.
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 while RL can.
"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 while RL can"
I will be satisfied if you just show us 1.
Stay in your lane, and state that you built a fast heuristic that works (finds good solutions but not optimal) in the problems you tried. Nobody can dispute this. But don't make claims you cannot support.
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 while RL can"
I will be satisfied if you just show us 1.
Stay in your lane, and state that you built a fast heuristic that works (finds good solutions but not optimal) in the problems you tried. Nobody can dispute this. But don't make claims you cannot support.
[deleted]
>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.
actually i guess they're shilling - not that there's that much of a differnce.
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.
They're two different methodologies that are most of the time applied to vastly different problems.
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.
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.
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?
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.
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.
[deleted]
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.
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.
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.
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.
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.
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.
Right, I get what an LP is. As I said in the other thread, I'm mainly trying to use charity to the opening post to find a way it can be meaningful. With an idea that mayhap you could use RL to try and explore a solution space that you don't know the penalty for non-compliance to a solution.
Specifically, use LP to craft a plan in an iteration of scenarios that is varying a cost function through iterations. I suspect I'm fumbling in the multi period planning realm more so than the RL one, here.
I further suspect, though, that it is more "if you can formalize your problem such that LP solves it, use LP." That is, the opening post was largely just nonsensical?
Specifically, use LP to craft a plan in an iteration of scenarios that is varying a cost function through iterations. I suspect I'm fumbling in the multi period planning realm more so than the RL one, here.
I further suspect, though, that it is more "if you can formalize your problem such that LP solves it, use LP." That is, the opening post was largely just nonsensical?
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?
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.
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.
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.
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.
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.
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.
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.
> 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 some continuity in the linear algebra, the changes in z should (I am avoiding doing the derivations) be small, and continuing to use the optimal x from before the changes should (again, some derivations are needed) be not far off (omitting details).
The feasible region is much like a diamond with flat sides and sharp points (the extreme points).
Uh, let set F be the feasible region, i.e.,
F = {x | Ax = b, x >= 0}
Then the feasible region is convex, i.e., for x_1 and x_2 in the feasible region and t in [0,1],
tx_1 + (1 - t)x_2
(intuitively the points on the line between the two points x_1 and x_2) is also in the feasible region F.
So, easily there can be two extreme points x_1 and x_2 in F such that
z = cx_1 = cx_2
and both are optimal.
Then all points on the line between x_1 and x_2 will be feasible and optimal. So, now have infinitely many optimal points.
And it can be that x_1 is the only optimal point but after some small changes both x_1 and x_2 are optimal. And x_2 can be a long way from x_1.
Sooooo, the small changes resulted in a big change in the optimal points. And maybe after the change, x_2 is optimal but x_1 no longer is.
In this case, maybe LP does not look "robust", but that's usually not a big problem since after the small changes, likely in practice can still get by using the old optimal x_1.
I.e., just by continuity, the "small changes" will keep the changes in the feasible region F and the optimal value z small.
Ah, here is the good news: If raising 40,000 chickens (my father in law used to do that) and there is a small change in the prices of some of the feeds, after the small change might change suppliers (big change in x) for a savings in prices. Intuitively, the changes just showed that you are not very dependent on your old suppliers but have some alternatives that involve some big changes in x (maybe drop one supplier for another one) for about the same z. That big change in x looks not "robust" but is good news, right?
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 some continuity in the linear algebra, the changes in z should (I am avoiding doing the derivations) be small, and continuing to use the optimal x from before the changes should (again, some derivations are needed) be not far off (omitting details).
The feasible region is much like a diamond with flat sides and sharp points (the extreme points).
Uh, let set F be the feasible region, i.e.,
F = {x | Ax = b, x >= 0}
Then the feasible region is convex, i.e., for x_1 and x_2 in the feasible region and t in [0,1],
tx_1 + (1 - t)x_2
(intuitively the points on the line between the two points x_1 and x_2) is also in the feasible region F.
So, easily there can be two extreme points x_1 and x_2 in F such that
z = cx_1 = cx_2
and both are optimal.
Then all points on the line between x_1 and x_2 will be feasible and optimal. So, now have infinitely many optimal points.
And it can be that x_1 is the only optimal point but after some small changes both x_1 and x_2 are optimal. And x_2 can be a long way from x_1.
Sooooo, the small changes resulted in a big change in the optimal points. And maybe after the change, x_2 is optimal but x_1 no longer is.
In this case, maybe LP does not look "robust", but that's usually not a big problem since after the small changes, likely in practice can still get by using the old optimal x_1.
I.e., just by continuity, the "small changes" will keep the changes in the feasible region F and the optimal value z small.
Ah, here is the good news: If raising 40,000 chickens (my father in law used to do that) and there is a small change in the prices of some of the feeds, after the small change might change suppliers (big change in x) for a savings in prices. Intuitively, the changes just showed that you are not very dependent on your old suppliers but have some alternatives that involve some big changes in x (maybe drop one supplier for another one) for about the same z. That big change in x looks not "robust" but is good news, right?
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 also have to deal with the unknown adversaries of the system that will work against it, though? Not just, "we were sensitive to the costs of feed changing, but there is also now an avian flu going around and we have to kill our flock." A simulation is easy to imagine that does this and forces you to see what is next. Is that common in LP formulations?
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 also have to deal with the unknown adversaries of the system that will work against it, though? Not just, "we were sensitive to the costs of feed changing, but there is also now an avian flu going around and we have to kill our flock." A simulation is easy to imagine that does this and forces you to see what is next. Is that common in LP formulations?
> 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.
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.
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.
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.
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?
> 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.
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 :)
I'm pretty sure the main reason for throwing out old tools that still function in favor of the new hotness is developer boredom.
This is why my teams always provide explicit opportunities and spaces for professional development. People should have the opportunity to stretch and grow; if you don't provide those opportunities explicitly, then your most motivated employees will find them implicitly. And you can't afford to not keep your most motivated employees, so you'll end up paying with tech debt instead of Engineeer prof development time.
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.
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.
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.