Linear Programming for Fun and Profit
1–10 of 17 posts
Re: Linear Programming for Fun and Profit
#2> X = [x1, ..., Xn]: instances of each type to launch
Is this a continuous variable? Seems discrete to me. I am surprised it is solved by simplex.
Re: Linear Programming for Fun and Profit
#3Great to see this post here -- really enjoyed writing it! I think it's really cool how an algorithm from an operational research context can play a critical role in a high-availability large-scale cloud service.
Re: Linear Programming for Fun and Profit
#4Great to see this post here -- really enjoyed writing it! I think it's really cool how an algorithm from an operational research context can play a critical role in a high-availability large-scale cloud service.
LP is a shockingly good way to optimize a system. If you can put inputs/outputs into the correct form. Had an econ prof that loved these things for doing supply/demand maxima and minimum finding. He didnt outright say it but I think it was his current line of study when I was taking classes from him the 90s. I thought that, as he managed to bring it up in every class he taught.
Re: Linear Programming for Fun and Profit
#5> X = [x1, ..., Xn]: instances of each type to launch Is this a continuous variable? Seems discrete to me. I am surprised it is solved by simplex.
It's the answer, a vector of integers
Re: Linear Programming for Fun and Profit
#6> X = [x1, ..., Xn]: instances of each type to launch Is this a continuous variable? Seems discrete to me. I am surprised it is solved by simplex.
It's the answer, a vector of integers
Simplex cannot give a vector of integers though, unless the constraint matrix is unimodular. Maybe the integrality constraint was relaxed.
Re: Linear Programming for Fun and Profit
#7Earlier quoted context omitted.
It's the answer, a vector of integers
Simplex cannot give a vector of integers though, unless the constraint matrix is unimodular. Maybe the integrality constraint was relaxed.
You're right -- we do relax the integrality constraint, gaining performance at the expense of some precision, and we're generally able to paper over the difference at scheduling time. We've investigated integer linear programming for some use cases, but for solves to run quickly, we have to constrain the inputs significantly.
Re: Linear Programming for Fun and Profit
#8Neat article. I do wish it mentioned that there are polynomial time algorithms to solve linear programming problems. According to the Google ortools docs it has the option to use those as well (but not with the GLOP solver). Might be good for when simplex is struggling (https://developers.google.com/optimization/lp/lp_advanced)
Re: Linear Programming for Fun and Profit
#9Earlier quoted context omitted.
Simplex cannot give a vector of integers though, unless the constraint matrix is unimodular. Maybe the integrality constraint was relaxed.
You're right -- we do relax the integrality constraint, gaining performance at the expense of some precision, and we're generally able to paper over the difference at scheduling time. We've investigated integer linear programming for some use cases, but for solves to run quickly, we have to constrain the inputs significantly.
Thanks for the clarification. I guess it wouldn’t matter much if the numbers are large. Initially I thought they were mostly ones and zeros.
Re: Linear Programming for Fun and Profit
#10Earlier quoted context omitted.
Simplex cannot give a vector of integers though, unless the constraint matrix is unimodular. Maybe the integrality constraint was relaxed.
You're right -- we do relax the integrality constraint, gaining performance at the expense of some precision, and we're generally able to paper over the difference at scheduling time. We've investigated integer linear programming for some use cases, but for solves to run quickly, we have to constrain the inputs significantly.
If this is business critical for you, you may want to switch to a faster solver. Glop is very nice, but it would be reasonable to expect a commercial solver (Gurobi, XPress, COpt) to be 60x faster [1]. By the same measure, the best open source solvers (CLP, HiGHS) are 2-3x faster than Glop.
Actually, the commercial solvers are so fast that I would not be surprised if they solved the IP problem as fast as Glop solves the LP. (Yes, the theory says it is impossible, but in practice it happens.) The cost of a commercial solver is 10k to 50k per license.
[1] ... this 60x number has very high variance depending on the type of problem, but it is not taken out of nowhere, it comes from the Mittelmann LP benchmarks https://plato.asu.edu/ftp/lpopt.html There are also benchmarks for other types of problems, including IP, see the whole list here: https://plato.asu.edu/bench.html