[HN Gopher] Scaling up linear programming with PDLP
___________________________________________________________________
Scaling up linear programming with PDLP
Author : bookofjoe
Score : 206 points
Date : 2024-09-21 12:57 UTC (1 days ago)
(HTM) web link (research.google)
(TXT) w3m dump (research.google)
| bee_rider wrote:
| I 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 wrote:
| Preconditioning would only apply to approaches like interior
| point methods, where the condition number quickly approaches
| infinity.
| bee_rider wrote:
| I 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 wrote:
| There 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 wrote:
| I 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 wrote:
| Slightly off topic but does anybody have any resources for
| learning linear programming for business applications?
| nickpeterson wrote:
| I 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 wrote:
| Have you seen http://www.hakank.org/ ? Mostly about
| constraint programming, but definitely in the realm of
| operations research.
| nickpeterson wrote:
| I've stumbled across it a few times way back when I was
| looking at MRP stuff for an ERP I worked on. I remember it
| being a rare gem of a website. I'd throw away 99% of web
| pages if the ones remaining were all like this one. Thanks
| for the reminder!
| polivier wrote:
| I write blog posts about constraint programming from time to
| time. I always include a step-by-step description of the
| model, which makes it fairly easy to understand. Hopefully
| this can be of help for you: https://pedtsr.ca
| armanboyaci wrote:
| I recommend this blog:
| https://yetanothermathprogrammingconsultant.blogspot.com/?m=...
|
| Not all posts are business related but you can learn many
| practical tricks hard to find in books.
| tomas789 wrote:
| I add my +1 to this. I often come across this blog posts
| while working as a OR professional.
| pjot wrote:
| GAMS is such a wild language/environment.
|
| I don't know of anything better, but I'm currently reliving
| nightmares from my Masters
| currymj wrote:
| JuMP is comparably good I think. People reasonably don't
| want to add a new language to their stack. But if you're
| just formulating MPs it's as nice as anything, free, and
| you have a well designed modern programming language if you
| need it.
| currymj wrote:
| the Mosek Modeling Cookbook is really good for seeing the
| "tricks" of how to reformulate things as convex programs.
|
| https://docs.mosek.com/modeling-cookbook/index.html
|
| Not for total beginners though but great 201 level resource.
| nuclearnice3 wrote:
| If you can get your hands on informs publications.
|
| https://www.informs.org/Publications
| cashsterling wrote:
| I'd recommend getting the 9th or 10th edition of Introduction
| to Operations Research by Hillier and Lieberman. 9th:
| https://www.amazon.com/dp/0077298349 You can search for the
| 10th edition. Both are available used for less than 50 USD in
| good condition. The book covers a lot more than linear
| programming. A solution manual for both editions can be found
| on the internet.
|
| 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.
| bookofjoe wrote:
| 10th edition free here:
| https://s23.middlebury.edu/MATH0318A/Hillier10th.pdf
| syockit wrote:
| I'd say to be wary of sharing links to full textbooks
| unless you are really sure it's posted by the copyright
| owner. The authors could be best friends with the webmaster
| and allowed them to post it on their website, but the
| problem is with the publisher who may not have given
| consent.
| bookofjoe wrote:
| I assume you believe Sci-Hub should be shut down.
|
| https://litfl.com/sci-hub-pirate-paper-portal/
| kristopolous wrote:
| What do people on here use this stuff for? Are you building
| out large IT infrastructures? Sorry, this is all very new
| stuff to me.
| quantresearch1 wrote:
| In my work, I use Gurobi and other proprietary/free solvers
| to optimize some objectives big banks care about. It's not
| uncommon to use solvers in finance to optimize some metrics
| of a portfolio. A lot of people I have met in conferences
| optimize their supply chains (think things like: find the
| best pattern to draw the various pieces of my table in
| these planks of wood such that it minimizes wastes, find
| the best route to deliver my 100 packages...)
| kristopolous wrote:
| Right, the LEAN/TPS application is readily apparent for
| assembling physical goods.
|
| 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
| lm7272 wrote:
| initial margin?
| jethkl wrote:
| LPs (and MIPs) are used for scheduling, planning, and
| logistics. These are some of the earliest applications of
| LPs, dating to the 1930's and 1940's, and these
| applications are still relevant. The wikipedia page has a
| good overview of the history and utility of linear
| programming.
| https://en.wikipedia.org/wiki/Linear_programming
| kristopolous wrote:
| Yes, I took a math course on it way back in college but I
| haven't ever considered using it professionally. Heck in
| college I did it by hand.
|
| 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
| jethkl wrote:
| That's a clarifying response: I've applied (non)convex
| programming (LP, QP, MIP, etc) to all the above and a few
| more, all of which i'd classify as classical
| applications. Less traditional applications -- I'd like
| to explore these more --- include data envelopment
| analysis, which provides a framework for assessing the
| efficiency of processes based on 1 or more input metrics,
| and several ideas in papers published at NeurIPS and
| other conferences that integrate LPs into neural networks
| in various ways, including AUC maximization. I've also
| worked on first order methods to solve LPs, and while I'd
| like to continue in that direction, the area is very
| crowded with very good existing tools, new and emerging
| tools that are also often good, and very strong teams
| building on all of the above. One of the biggest
| challenges that I see in the OR space is that it requires
| human expertise to leverage the technology.
| jeffbee wrote:
| You could just grab or-tools and work through their example
| problems, then extend it to something in your area of interest.
| The Python APIs are easy to experiment with.
| chris_nielsen wrote:
| Applied Mathematical Programming
| https://web.mit.edu/15.053/www/AMP.htm
| l33t7332273 wrote:
| I second this blog. The comparison of (10 different!) MIP
| modeling techniques for piecewise linear functions is more
| complete than any I've seen.
| ant6n wrote:
| Isnt this something that could be useful for consulting? I've
| occasionally considered trying to help businesses model MILPs
| to help solve their problems, but its so specialist that
| finding good matches is like the actual problem. I wonder how
| specialists like milp experts find clients.
| wodenokoto wrote:
| We needed to get a project based off of ORTools, that some
| consultants had left us, working and expanded.
|
| 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.
| loehnsberg wrote:
| Largest applications may well be in power systems (economic
| dispatch, unit commitment), material requirements planning,
| transportation networks, but linear programming can also be
| used to fit functions, think constrained regression with L1
| loss.
| cschmidt wrote:
| The "Model Building in Mathematical Programming" book by
| Williams is unique in that it talks about how to formulate LP
| and MILP problems, rather than focusing on the algorithm side
| of how the simplex algorithm works. That's nice to know, but
| not really necessary. You really need to get some intuition on
| thinking about objectives and constraints.
|
| https://www.wiley.com/en-us/Model+Building+in+Mathematical+P...
| taeric wrote:
| https://a.co/d/cpmi8dO was a fun book to me.
| eh_why_not wrote:
| Can we post clean and direct links to resources here, instead
| of those obscure links with hidden tracking?
| DominikPeters wrote:
| In 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 wrote:
| They link to three of their papers that have more details.
| optcoder wrote:
| The 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/pdf/2312.14832. It is CPU vs GPU, though,
| not sure how fair it is.
| thxg wrote:
| I 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
| sitkack wrote:
| Hans D Mittlemann, you are my top dude when it comes to web
| design. A salute your aesthetic.
|
| [1] https://plato.asu.edu/
| whatever1 wrote:
| FYI the table does not include the commercial top dogs (ibm
| cplex, gurobi, Fico Xpress), since due to politics they all
| withdrew
| thxg wrote:
| Indeed those are the "big four" solver businesses in the
| West, and also probably the most reliably-good solvers.
| But by the time Gurobi withdrew from the benchmarks (a
| few weeks ago), COpt was handily beating them in the LP
| benchmarks, and closing down on them in MIP benchmarks.
| Solver devs like to accuse each other of gaming
| benchmarks, but I'm not convinced anyone is outright
| cheating right now. Plus, all solver companies have
| poached quite a bit from each other since cplex lost all
| its devs, which probably equalizes the playing field. So
| overall, I think Mittelmann benchmarks still provide a
| good rough estimate of where the SOTA is.
| dsfcxv wrote:
| Their numerical results with GPUs, compared to Gurobi, are
| quite impressive [1]. In my opinion (unless I'm missing
| something), the key benefits of their algorithms lie in the
| ability to leverage GPUs and the fact that there's no need to
| store factorization in memory. However, if the goal is to solve
| a small problem on a CPU that fits comfortably in memory, there
| may be no need to use this approach.
|
| [1] https://arxiv.org/pdf/2311.12180
| thxg wrote:
| I agree that their results are impressive. Just to be clear,
| however:
|
| 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.
| dsfcxv wrote:
| hmm... I am reading [1] right now. When looking at their
| Table 7 and Table 11 in [1], they report comparison results
| with Gurobi presolve enabled and 1e-8 error. Do I miss
| anything?
|
| Their performance isn't quite as good as Gurobi's barrier
| method, but it's still within a reasonable factor, which is
| impressive.
| thxg wrote:
| Regarding presolve: When they test their solver "with
| presolve", they use _Gurobi_ 's presolve as a
| preprocessing step, then run their solver on the output.
| To be clear, this is perfectly fair, but from the
| perspective of "can I switch over from the solver I'm
| currently using", this is a big caveat.
|
| 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!
| GistNoesis wrote:
| Let'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 wrote:
| Maybe 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 wrote:
| LPaaS?
|
| 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).
| RayVR wrote:
| Proprietary 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.
| quantresearch1 wrote:
| If you can beat the best solvers out there by a significant
| margin, I would say it's worth 10's of thousands a year. Speed
| is one aspect of it, but it could also be you are able to solve
| problems other solvers cannot solve. Depending on which
| companies you are targeting, I would not necessarily recommend
| going the route where the user upload their data to you and you
| solve it for them as many companies cannot legally share their
| clients' data (which is often part of the optimization). You
| can package the software into a linux/windows executable and
| sell it at a yearly subscription. It's worth noting that there
| are companies that will not be able to switch easily as they
| build all of their models around a specific solver API (say
| gurobipy)
| snowstormsun wrote:
| Just share it for free. Science doesn't work that way.
| cschmidt wrote:
| I 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 wrote:
| I 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 wrote:
| Branch 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.
| pkhuong wrote:
| First order methods like PDLP tend to warm start much
| better than interior point. I'm confident Applegate (of
| Concorde fame, and who worked on huge MIPs at Google when I
| was there) is thinking about integration in MIP solvers.
| cschmidt wrote:
| Cool, that's just what I was wondering.
| imtringued wrote:
| You'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 wrote:
| This sounds interesting. Mind sharing an instance of these hard
| small problems?
___________________________________________________________________
(page generated 2024-09-22 23:01 UTC)