4 ms·

The OP and the discussion is sround technical implementation, but I am interesred in the analysis part of LP. I wanted to use LP to optimize a budget but my se

by blahi 10y ago

The OP and the discussion is sround technical implementation, but I am interesred in the analysis part of LP. I wanted to use LP to optimize a budget but my senior coleague said that LP is just too damn hard in the real world. Is this true? Is there a textbook that goes over practical applications of LP?

Pamar 10y ago
I am not sure what your colleague means with "too damn hard" - I used it once in production code to optimize distribution of lots on an assembly line, for example. That was a COBOL program dynamically preparing the equations and then calling a C routine (copied straight out of the "Numerical Recipes in C") and that was all. Of course you have to get a bit of practice about how to represent your problem in terms of equation and objective function, and yes, there are cases where it can become quite complicated and/or become intractable due to variable explosion... but it is not necessarily so. (I cannot suggest a book, sorry, but if you want to contact me in email we can go over your problem in general terms and see if I can provide some general advice, maybe?)
ColinWright 10y ago
I am surprised that your senior colleague says it's "too damn hard." Are they referring to the conversion of your data into the right format, or are they referring to getting an implementation running? The latter is fairly straight-forward, the former depends on how clean and convertible your existing data are. If your data are currently messy, you need to clean it up anyway. There will be political issues with doing work your senior colleague says is not possible, but if you can solve - or avoid - the political problems, learning how to do this, and then doing it, will be good for your personal development. Warning: I suspect the political problems will actually be the most difficult part.
- blahi 10y ago
  The data is squeaky clean, accounting-like data. Getting it to right format is a few lines of R. What he says is too difficult is putting in place all the right constraints. He says that it is very easy to miss a necessary constraint and this will obviously blow up your solution. How can I examine the solution to make sure it would be valid? The data consists of tens/hundreds of thousands of line items which compete for the same budget and need to meet some (fairly simple) metrics. Line items have a hidden dependency between them, so presumably the solver can scrap some items which will in turn make others (possibly the ones with the best metrics) tank too.
  - ColinWright 10y ago
    Now I'm less surprised. If you don't know all the constraints, explicitly and up front as part of your data, then it will be difficult. How is it being done now? How close to optimal is the current version/solution? The constraints form part of your data, and it sounds like they are not squeaky clean. With all computer optimisation, you need to make your data clean, clear, and complete. This can sometimes be done by simply trying it and seeing what the obvious flaws are in the proposed solutions, sometimes that's infeasible.
    - blahi 10y ago
      People examine data manually in reports currently. If an item turns a profit, leave it, no yield optimization. If it's in the red, stop it. If it's around break-even, schedule it for examination to see if you can turn it green. No idea how close to optimal it is. I'd imagine not at all.
      - ColinWright 10y ago
        OK, I'm looking in from the outside, and I know all too well how these sorts of situations arise. However, it sounds to me a lot like the managers have largely lost control of the situation, and they are limping along doing the best they can with a system that has evolved from something system into a monster. That happens. The challenge is how to make it better. Thinking of it like software, there are no unit tests, and touching anything runs the risk of breaking everything. The usual way to proceed is to find a small section that you can write tests for, and then gradually transform into something you understand. The equivalent here might be to find a small collection of items that are largely independent of the rest of the product line, and see if you can bring that under control. However, I don't know your context, and I do appreciate that wholesale changes might well be risky. The question is, can you even make a start on a small section? If not, all is lost and the system will limp along as is. But if progress is desirable, maybe there is a way to start. Given that your senior colleague has actually spoken with you about this, maybe you can open that conversation, proposing it as a gradual way to make the system more efficient, profitable, and to reduce the existing risks. Again, on the political side, make sure they don't feel threatened, bring them on board as a partner, make it clear that you want to learn from them, and couch it all in terms of reducing risk to the company in return for a small outlay in time and effort. See it as an opportunity for you to learn, them to gain credit, and the company to become stronger. These are my thoughts - you must adapt them to your context.
arethuza 10y ago
I remember watching an Open University maths program on the practical application of linear programming when I was a high school - it was for blending food ingredients to meet the required nutritional requirements. That was probably the late 70s!
merraksh 10y ago
It could be that the current method (i.e. human solves it by making a decision for each item) could be proved to give an optimal solution. However, if that is not the case, the hardest part will be to get the right model. There are very competitive open source solvers for LP with 10ˆ5 or even 10ˆ6 variables/constraints (https://projects.coin-or.org/Clp https://projects.coin-or.org/Clp), so the true limit here is formulating the model correctly. There are various optimization modeling languages out there, also in the open-source arena. As for getting the model right, some trial-and-error approach should work: 1) if the solution violates a constraint you hadn't thought of, just add it to the formulation and re-solve; 2) if the solution is too conservative, then there might be a constraint that's too restrictive (you can check which constraints are active, i.e. restricting, at the optimal solution you found), so just eliminate it or relax it.
thanatropism 10y ago
This is pretty good, although not business-oriented necessarily. http://www.springer.com/us/book/9783540306979 http://www.springer.com/us/book/9783540306979

by blahi 10y ago

Pamar 10y ago

I am not sure what your colleague means with "too damn hard" - I used it once in production code to optimize distribution of lots on an assembly line, for example. That was a COBOL program dynamically preparing the equations and then calling a C routine (copied straight out of the "Numerical Recipes in C") and that was all. Of course you have to get a bit of practice about how to represent your problem in terms of equation and objective function, and yes, there are cases where it can become quite complicated and/or become intractable due to variable explosion... but it is not necessarily so. (I cannot suggest a book, sorry, but if you want to contact me in email we can go over your problem in general terms and see if I can provide some general advice, maybe?)

ColinWright 10y ago

I am surprised that your senior colleague says it's "too damn hard." Are they referring to the conversion of your data into the right format, or are they referring to getting an implementation running? The latter is fairly straight-forward, the former depends on how clean and convertible your existing data are. If your data are currently messy, you need to clean it up anyway. There will be political issues with doing work your senior colleague says is not possible, but if you can solve - or avoid - the political problems, learning how to do this, and then doing it, will be good for your personal development. Warning: I suspect the political problems will actually be the most difficult part.

blahi 10y ago
The data is squeaky clean, accounting-like data. Getting it to right format is a few lines of R. What he says is too difficult is putting in place all the right constraints. He says that it is very easy to miss a necessary constraint and this will obviously blow up your solution. How can I examine the solution to make sure it would be valid? The data consists of tens/hundreds of thousands of line items which compete for the same budget and need to meet some (fairly simple) metrics. Line items have a hidden dependency between them, so presumably the solver can scrap some items which will in turn make others (possibly the ones with the best metrics) tank too.
- ColinWright 10y ago
  Now I'm less surprised. If you don't know all the constraints, explicitly and up front as part of your data, then it will be difficult. How is it being done now? How close to optimal is the current version/solution? The constraints form part of your data, and it sounds like they are not squeaky clean. With all computer optimisation, you need to make your data clean, clear, and complete. This can sometimes be done by simply trying it and seeing what the obvious flaws are in the proposed solutions, sometimes that's infeasible.
  - blahi 10y ago
    People examine data manually in reports currently. If an item turns a profit, leave it, no yield optimization. If it's in the red, stop it. If it's around break-even, schedule it for examination to see if you can turn it green. No idea how close to optimal it is. I'd imagine not at all.
    - ColinWright 10y ago
      OK, I'm looking in from the outside, and I know all too well how these sorts of situations arise. However, it sounds to me a lot like the managers have largely lost control of the situation, and they are limping along doing the best they can with a system that has evolved from something system into a monster. That happens. The challenge is how to make it better. Thinking of it like software, there are no unit tests, and touching anything runs the risk of breaking everything. The usual way to proceed is to find a small section that you can write tests for, and then gradually transform into something you understand. The equivalent here might be to find a small collection of items that are largely independent of the rest of the product line, and see if you can bring that under control. However, I don't know your context, and I do appreciate that wholesale changes might well be risky. The question is, can you even make a start on a small section? If not, all is lost and the system will limp along as is. But if progress is desirable, maybe there is a way to start. Given that your senior colleague has actually spoken with you about this, maybe you can open that conversation, proposing it as a gradual way to make the system more efficient, profitable, and to reduce the existing risks. Again, on the political side, make sure they don't feel threatened, bring them on board as a partner, make it clear that you want to learn from them, and couch it all in terms of reducing risk to the company in return for a small outlay in time and effort. See it as an opportunity for you to learn, them to gain credit, and the company to become stronger. These are my thoughts - you must adapt them to your context.

arethuza 10y ago

I remember watching an Open University maths program on the practical application of linear programming when I was a high school - it was for blending food ingredients to meet the required nutritional requirements. That was probably the late 70s!

merraksh 10y ago

It could be that the current method (i.e. human solves it by making a decision for each item) could be proved to give an optimal solution. However, if that is not the case, the hardest part will be to get the right model. There are very competitive open source solvers for LP with 10ˆ5 or even 10ˆ6 variables/constraints (https://projects.coin-or.org/Clp https://projects.coin-or.org/Clp), so the true limit here is formulating the model correctly. There are various optimization modeling languages out there, also in the open-source arena. As for getting the model right, some trial-and-error approach should work: 1) if the solution violates a constraint you hadn't thought of, just add it to the formulation and re-solve; 2) if the solution is too conservative, then there might be a constraint that's too restrictive (you can check which constraints are active, i.e. restricting, at the optimal solution you found), so just eliminate it or relax it.

thanatropism 10y ago

This is pretty good, although not business-oriented necessarily. http://www.springer.com/us/book/9783540306979 http://www.springer.com/us/book/9783540306979