Linear Programming for Fun and Profit
13 comments
·May 9, 2025cweld510
sumtechguy
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.
underanalyzer
Neat 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)
stncls
You're right, but it's very subtle and complicated.
In theory, the simplex method is not known to be polynomial-time, and it is likely that indeed it is not. Some variants of the simplex method have been proven to take exponential time in some worst cases (Klee-Minty cubes). What solvers implement could be said to be one such variant ("steepest-edge pricing"), but because solvers have tons of heuristics and engineering, and also because they work in floating-point arithmetic... it's difficult to tell for sure.
In practice, the main alternative is interior-point (aka. barrier) methods which, contrary to the simplex method, are polynomial-time in theory. They are usually (but not always) faster, and their advantage tends to increase for larger instances. The problem is that they are converging numerical algorithms, and with floating-point arithmetic they never quite 100% converge. By contrast, the simplex method is a combinatorial algorithm, and the numerical errors it faces should not accumulate. As a result, good solvers perform "crossover" after interior-point methods, to get a numerically clean optimal solution. Crossover is a combinatorial algorithm, like the simplex method. Unlike the simplex method though, crossover is polynomial-time in theory (strongly so, even). However, here, theory and practice diverge a bit, and crossover implementations are essentially simplified simplex methods. As a result, in my opinion, calling iterior-point + crossover polynomial-time would be a stretch.
Still, for large problems, we can expect iterior-point + crossover to be faster than the simplex method, by a factor 2x to 10x.
There is also first-order methods, which are getting much attention lately. However, in my experience, you should only use that if you are willing to tolerate huge constraint violations in the solution, and wildly suboptimal solutions. Their main use case is when other solvers need too much RAM to solve your instance.
underanalyzer
Very interesting! Thanks for the reply. I wonder if they tried these other solvers and decided they were either too slow b/c their problems were too small or the answers were too inaccurate
ayhanfuat
> 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.
Frummy
It's the answer, a vector of integers
ayhanfuat
Simplex cannot give a vector of integers though, unless the constraint matrix is unimodular. Maybe the integrality constraint was relaxed.
cweld510
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.
null
Great 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.