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.
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.
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.
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.
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.
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!
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.
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…”
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.
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.
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.
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.
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.
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.
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.
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.
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.
if you have a license for a good fast solver already for some reason, it can be very effective to reduce some NP-hard problems to integer programming.
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.
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
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.
In a professional context, I use it to help a client (chemicals company) optimize their deliveries to customers. They have > 100 production sites and thousands of customers, so LP is used to allocate customers to production sites based on the product-cost and availability at supply site and trucking costs. We have evaluated multiple solvers (Gurobi/ Llamasoft/ GAMS/ LocalSolver etc) for optimizing deliveries, as well as evaluating the cost impact of changes to the delivery network.
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...)
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
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.
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.
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
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!
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.
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.
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.
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.
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.
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 ?
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)
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).
True. 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.
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
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.
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.
GLPK 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), 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.
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.
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
Hans D Mittlemann, you are my top dude when it comes to web design. A salute your aesthetic.
[1] https://plato.asu.edu/
FYI the table does not include the commercial top dogs (ibm cplex, gurobi, Fico Xpress), since due to politics they all withdrew
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.
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
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.
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.
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!
They link to three of their papers that have more details.
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.
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?
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.
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.
Preconditioning would only apply to approaches like interior point methods, where the condition number quickly approaches infinity.
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.
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.
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.
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.
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.
Cool, that’s just what I was wondering.
Slightly off topic but does anybody have any resources for learning linear programming for business applications?
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.
10th edition free here: https://s23.middlebury.edu/MATH0318A/Hillier10th.pdf
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.
I assume you believe Sci-Hub should be shut down.
https://litfl.com/sci-hub-pirate-paper-portal/
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.
if you have a license for a good fast solver already for some reason, it can be very effective to reduce some NP-hard problems to integer programming.
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.
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
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
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.
In a professional context, I use it to help a client (chemicals company) optimize their deliveries to customers. They have > 100 production sites and thousands of customers, so LP is used to allocate customers to production sites based on the product-cost and availability at supply site and trucking costs. We have evaluated multiple solvers (Gurobi/ Llamasoft/ GAMS/ LocalSolver etc) for optimizing deliveries, as well as evaluating the cost impact of changes to the delivery network.
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...)
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
initial margin?
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.
GAMS is such a wild language/environment.
I don’t know of anything better, but I’m currently reliving nightmares from my Masters
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.
I add my +1 to this. I often come across this blog posts while working as a OR professional.
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.
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
Have you seen http://www.hakank.org/ ? Mostly about constraint programming, but definitely in the realm of operations research.
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!
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...
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.
https://a.co/d/cpmi8dO was a fun book to me.
Can we post clean and direct links to resources here, instead of those obscure links with hidden tracking?
My 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
Book title: A Gentle Introduction to Optimization by by B. Guenin (Author), J. Könemann (Author), L. Tunçel (Author)
Applied Mathematical Programming https://web.mit.edu/15.053/www/AMP.htm
I second this blog. The comparison of (10 different!) MIP modeling techniques for piecewise linear functions is more complete than any I’ve seen.
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.
If you can get your hands on informs publications.
https://www.informs.org/Publications
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.
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.
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.
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 ?
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)
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).
If you (or your client) are ok with your data going off premises.
True. 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.
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
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.
Just share it for free. Science doesn't work that way.
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.
GLPK 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), 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.
This sounds interesting. Mind sharing an instance of these hard small problems?
[flagged]