Scaling up linear programming with PDLP
research.google
research.google
PDLP is targeted at instances for which factorizations won't fit in memory. I think their idea for now is to give acceptable solutions for gigantic instances when other solvers crash.
1. They compare their solver with a 1e-4 error tolerance to Gurobi with 1e-6. This may seem like a detail, but in the context of how typical LPs are formulated, this is a big difference. They have to do things this way because their solver simply isn't able to reach better accuracy (meanwhile, you can ask Gurobi for 1e-9, and it will happily comply in most cases).
2. They disable presolve, which is 100% reasonable in a scientific paper (makes things more reproducible, gives a better idea of what the solver actually does). If you look at their results to evaluate which solver you should use, though, the results will be misleading, because presolve is a huge part of what makes SOTA solvers fast.
Their performance isn't quite as good as Gurobi's barrier method, but it's still within a reasonable factor, which is impressive.
They indeed report being 5x slower than Gurobi at 1e-8 precision on Mittelmann instances, which is great. Then again, Mittelmann himself reports them as 15x off COpt, even when allowed to do 1e-4. This is perfectly explainable (COpt is great at benchmarks; there is the presolve issue above; the Mittelmann instance set is a moving target), but I would regard the latter number as more useful from a practitioner's perspective.
This is not to diminish PDLP's usefulness. If you have a huge instance, it may be your only option!
ILU0 is practically free, right?
If you have a problem that's small enough to factorize and solve, that's great. That probably is the best approach. This doesn't scale in parallel. For really big problems, iterative methods are the only game in town.
It's all about knowing the range of methods that are applicable to your problem and the regimes in which they operate best. There's no one-size-fits-all solution.
Not all posts are business related but you can learn many practical tricks hard to find in books.
I don’t know of anything better, but I’m currently reliving nightmares from my Masters
https://docs.mosek.com/modeling-cookbook/index.html
Not for total beginners though but great 201 level resource.
A good "free-pdf" optimization book, to support the above is, Algorithms for Optimization by Kochenderfer & Wheeler ( https://algorithmsbook.com/optimization/ ). It has a chapter on constrained linear optimization with Julia code and is a good secondary resource. Kochenderfer, Wheeler, and colleagues also have two other free optimization books that are a little more advanced. It is exceptionally cool that they make the high quality PDF freely available; more authors in the technical space are making their books freely available as pdf and I applaud them for it.
But do people use it say for large scale software which needs to be tested, certified, translated, deployed, etc? I can imagine such orchestration but I've never seen it professionally. Maybe I just haven't worked at the proper companies
I've never had to say, help design a $100 million server farm. I've had a desire recently to strive to be that level of professional.
My question was more about in the hn world where is this stuff used
also, one interesting application related to data science is to embed a machine learning model (usually regression, maybe decision tree or neural network) inside the integer program, and then maximize over its inputs. this can let you characterize worst-case behavior, or answer questions like "how must a user change their features to flip the prediction?".
solvers are so expensive that MIPs will probably never become part of mainstream data science, but they can be very powerful beyond classic OR problems.
After mocking about for a while getting nowhere, we took the optimization course on coursera from Melbourne University and were quite happy with how it helped us move along.
https://www.wiley.com/en-us/Model+Building+in+Mathematical+P...
Clean link: https://www.amazon.com/dp/1107658799
Book title: A Gentle Introduction to Optimization by by B. Guenin (Author), J. Könemann (Author), L. Tunçel (Author)
This isn't even a contrived problem to trick the LP solver. It is a grossly oversimplified version of the actual problem, which could have millions to billions of variables and even that version would be a grossly oversimplified version of the one based on the LPCC problem, aka linear programming with complementarity constraints so that I can model equilibrium conditions.
It slowly dawns upon me that LP/LPCC are highly nonviable for what I'm trying to do, which is kind of funny, because the discipline itself pretends that equilibrium is easy and automatic.
GLPK should not be used as a guide for the general field. The commercial solvers will do infinitely better than GLPK.
Optimisation fits the service model neatly: Submit your LP instance in some standard format, wait while it chugs away, then download the result (objective function value and variable assignments).
One day homomorphic encryption will solve all of this properly, but my understanding is we're a long way from that.
Being able to solve bigger problems faster than someone else might give you a competitive advantage in some existing business but wouldn’t be the business in and of itself.