6 ms·

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 ex

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.

taeric 3y 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.
- whatever1 3y ago
  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.
  - taeric 3y ago
    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?
    - whatever1 3y ago
      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.
      - taeric 3y ago
        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.
    - graycat 3y ago
      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.
- graycat 3y ago
  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.
  - taeric 3y ago
    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?
- graycat 3y ago
  > 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?
  - taeric 3y ago
    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?

taeric 3y 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.

whatever1 3y ago
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.
- taeric 3y ago
  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?
  - whatever1 3y ago
    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.
    - taeric 3y ago
      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.
  - graycat 3y ago
    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.
graycat 3y ago
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.
- taeric 3y ago
  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?
graycat 3y ago
> 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?
- taeric 3y ago
  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?