5 ms·
Scaling up linear programming with PDLP
- janetgabriel 2y ago♠ ♠ Am here to thank Dr Osaka for helping get back my ex Dr Osaka ma a healer spiritual reader and professional spell caster with more than 20 years experience worry no more Dr Osaka gives solution to any kind of problem. Cleansing Reading Love spell Spell caster Curse removal Black magic/revenge spells hex spell Ex back spell and lot more visit his Facebook page for help Or whatsapp number +2349024827182 ::Email.drosakalovespelltemple217@gmail.com https://www.facebook.com/profile.php?id=100089677235386 https://www.facebook.com/profile.php?id=100089677235386
- bee_rider 2y agoI often see the sentiment, essentially, a method is much better because it uses only matvecs (rather than factorize and solve). This always confuses me, because the game for numerical linear algebra folks is inventing funky preconditioners to fit their problem, right? Unless people are subtly saying “our new method converges incredibly quickly…” ILU0 is practically free, right?
- pkhuong 2y agoPreconditioning would only apply to approaches like interior point methods, where the condition number quickly approaches infinity.
- pkhuong 2y agoI forgot some first-order methods also solve a projection problem, and I believe I've seen some work on preconditioning there.
- bee_rider 2y agoI wonder if they put any matrices in the suitesparse collection, or anything like that. It would be a nice fun weekend project to just play around with them.
- sfpotter 2y agoThere are tons of different games to play. Designing a preconditioner that's specific to the problem being solved can help you beat incomplete LU, often by a substantial (even asymptotic) margin. 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.
- bee_rider 2y agoI agree, I was just using ilu as sort of a well known example. Also, because ILU0 has no fill-in, it should (IMO) be considered the “baseline” in the sense that not trying it should be justified somehow.
- raidicy 2y agoSlightly off topic but does anybody have any resources for learning linear programming for business applications?
- taeric 2y agohttps://a.co/d/cpmi8dO https://a.co/d/cpmi8dO was a fun book to me.
- eh_why_not 2y agoCan we post clean and direct links to resources here, instead of those obscure links with hidden tracking?
- taeric 2y agoMy apologies on that. Oddly, this is why I don't typically post from my phone, as it is far easier for me to get the clean link that way. Clean link: https://www.amazon.com/dp/1107658799 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)
- nickpeterson 2y agoI really wish I could find solid websites/blogs/resources for operations research, mathematical planning, linear programming, etc aimed at regular software engineers. I feel like a lot of the really crazy parts of codebases often derive from inexperience with these kinds of tools.
- colelyman 2y agoHave you seen http://www.hakank.org/ http://www.hakank.org/ ? Mostly about constraint programming, but definitely in the realm of operations research.
- nickpeterson 2y ago
- Shopper 2y ago[flagged]
- DominikPeters 2y agoIn this post, I don’t see any comparisons of their solver to other LP solvers on benchmarks, so it’s difficult to know how useful this is.
- sfpotter 2y agoThey link to three of their papers that have more details.
- optcoder 2y agoThe three linked papers seem to be old, but the broader impact section mentioned cupdlp, which is more recent and has interesting numerical comparisons with commercial solvers: https://arxiv.org/abs/2311.12180 https://arxiv.org/abs/2311.12180, https://arxiv.org/pdf/2312.14832 https://arxiv.org/pdf/2312.14832. It is CPU vs GPU, though, not sure how fair it is.
- thxg 2y agoI think it's partially excusable. Most LP solvers target large-scale instances, but instances that still fit in RAM. Think single-digit millions of variables and constraints, maybe a billion nonzeros at most. PDLP is not designed for this type of instances and gets trounced by the best solvers at this game [1]: more than 15x slower (shifted geometric mean) while being 100x less accurate (1e-4 tolerances when other solvers work with 1e-6). 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] https://plato.asu.edu/ftp/lpfeas.html https://plato.asu.edu/ftp/lpfeas.html
- GistNoesis 2y agoLet's say you discover a new technique to solve a generic problem like Linear Programming faster for bigger instances (like PDLP). How much is it worth ? How do you turn it into cold hard cash ? How do you work developing it further with other people without revealing your secret sauce ?
- user070223 2y agoMaybe ask your customer how much does it worth to them? You don't have to reveal the secret sauce, provide an API to your server to keep the algorithm IP. Of course there might be race to the bottom eventually like any busniess with zero marginal cost
- akoboldfrying 2y agoLPaaS? 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).
- mjcohen 2y agoIf you (or your client) are ok with your data going off premises.
- akoboldfrying 2y agoTrue. It might be possible to obfuscate in various ways, e.g., by replacing each variable with k fresh variables and only caring about their sum. But this makes your instance bigger (thus more expensive) and is maybe undone anyway by all their clever presolve tricks. One day homomorphic encryption will solve all of this properly, but my understanding is we're a long way from that.
- RayVR 2y agoProprietary optimization software is very niche and very expensive but I really doubt a single innovation, unless really significant, could justify the cost. 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.
- cschmidt 2y agoI wonder if this technique works well in branch and bound for Mixed Integer Linear Programming applications. They seem to be just applying it to plain LP applications. While there certainly are some use cases for large LPs, it seems like MILP is where the action is.
- larrydag 2y agoI don't see why not. Mixed Integer usually involves ways of setting up the variables for optimization. PDLP appears to use a lot of presovling which I'm sure helps to establish those bounds whether continuous or integer variables.
- cschmidt 2y agoBranch and bound is all about changing the bounds on a given fractional variable and resolving. It wasn't clear whether you could re-start from the previous solution with the new bound and quickly reoptimize.
- imtringued 2y agoYou're all so lucky your problems can be solved quickly. I seemingly have hit the worst possible problem for ILP. Admittedly I am just testing things in GLPK, but still, solving the ILP problem at problem size n=6 does not terminate. GLPK can solve the LP relaxation up to n=50, but it gets unbearably slow. 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.
- petters 2y agoThis sounds interesting. Mind sharing an instance of these hard small problems?
- BrannonKing 2y agoGLPK or GLPK_MI? GLPK is probably the worst tool you could pick. I tried it before on some of my problems, and it would not ever finish. Use OR-Tools, if it will work for your problem, or maybe one of the other free solvers with CVXpy will help you (https://www.cvxpy.org/tutorial/solvers/index.html https://www.cvxpy.org/tutorial/solvers/index.html), if you really need a free tool. GLPK should not be used as a guide for the general field. The commercial solvers will do infinitely better than GLPK.