27
$\begingroup$

Like many who participate in this site, I work on projects in both operations research (OR) and statistics/machine learning (ML). The different states of open source software in these fields are often discouraging as an OR professional.

In statistics, the research culture encourages researchers to implement their contributions in the domain-specific language R, so that practitioners have access to working software alongside a whitepaper.

In ML, companies like Google and Facebook spend gobs of money to develop open source tools like TensorFlow and PyTorch, which provide state-of-the-art ML tools to the masses.

The state of open source software in statistics and ML allows incremental contributions by individual researchers to be quickly incorporated and utilized by their research communities.

But in OR (and integer programming and combinatorial optimization in particular), Gurobi Optimizer and CPLEX have a stranglehold on the state of the art. Using an open source solver means you are leaving performance gains on the table. The result is that academic research in these areas has less impact, because anyone who wants to use the research must pay a small fortune in licensing fees. It's discouraging, and I believe it is one of the reasons that ML and statistics are growing increasingly popular (and perceived as an increasingly valuable skill set) relative to OR.

What explains the difference in open source software cultures between these fields? What can we do to make it better, so that we can get our work into the hands of more people who can use it?

Disclaimer: There are a number of fantastic open source projects in OR, which deserve to be celebrated. Off the top of my head (in optimization), examples include CBC/CLP, HiGHS, IPOPT, and the entire COIN-OR effort. I certainly don't mean to minimize the contributions of these projects, but the fact remains that in integer programming and combinatorial optimization, open source software lags behind its proprietary alternatives. This trend doesn't hold in other fields.


Edit: I've accepted the answer that I found most convincing. However, one aspect of the original question that hasn't yet been addressed very well is how to make it better. I'm still very interested in hearing suggestions for how to improve the state of open source software in our field, in case anyone would like to add additional answers.

$\endgroup$
8
  • 1
    $\begingroup$ Google is also spending some money to develop open-source tools for OR (OR-tools). Maybe the reason is that OR is less popular than ML, and therefore these companies prefer allocating more resources to ML $\endgroup$
    – fontanf
    Jan 5 at 18:53
  • 4
    $\begingroup$ What about database software? There are a lot of good open-source databases and database tools, but are they competitive with commercial database packages on very large and/or very complex databases? $\endgroup$
    – prubin
    Jan 5 at 19:58
  • 1
    $\begingroup$ See this question $\endgroup$
    – EhsanK
    Jan 5 at 21:44
  • 1
    $\begingroup$ S and S-Plus were commercial products predating "R". The language "R" was created as the "poor man's" S-Plus (sort of like Octavie to MATLAB) . Interestingly, unlike MATLAB, it went on to eclipse S-Plus, to the point that most users of "R" have never even heard of S or S-Plus. Aside from the "different eras" theory in some of the answers, there could also be a random component of what caught on and what didn't. $\endgroup$ Jan 6 at 16:36
  • 3
    $\begingroup$ It is not true that you have to spend a fortune to do research using Gurobi, CPLEX or Xpress solvers. They all offer free of charge licenses for academic use. $\endgroup$ Jan 7 at 15:58

5 Answers 5

31
$\begingroup$

As someone who uses a lot of commercial/open-source OR software and incidentally tried coding my own solver, the underlying question is that of continued funding and support.

As mentioned in another answer, LP/MIP solvers have been around for over 30 years (fun fact: technically, solving LPs and MIPs pre-dates software itself). This means continued development over several decades, with incremental improvements every year summing up to Richard's "brutal performance". In my view, the main difference between open-source and commercial tools is there: the latter benefit from continuous support and improvements over many years, while the former often stale when their main developer retires or moves on.

Not everything is grim though. SCIP (albeit not technically open-source) has institutional support from Zib and several industrial partners. Google's OR-Tools is open-source. More recently, the HiGHS team has managed to find some industrial partners to fund (part of?) the development.

This raises the following question: why do open-source ML/Stats tool get so much company support compared to the OR ones? Why does Google invests so much money in TensorFlow but doesn't sell licenses? And why isn't there a similar situation in OR?

Answer 1: culture. TensorFlow is pre-dated by Theano (now discontinued), whose academic devs wanted to be open-source. So when TensorFlow (and later Pytorch) came around, people had a strong open-source alternative, hence, there was less value in keeping it closed-source. The ML community is now very pro open-source indeed.

Answer 2: intrinsic value. In ML, the core value is not in the ML algorithm itself, it's in the data you feed it and the computing power you have. Google did open-source TF, but you don't see Google (or any other big player) open-source their data. In contrast, in OR, there is a lot of value in being able to solve the problem in the first place. Data still plays a huge role, but the algorithms carry relatively more weight than in ML.


Re: "How to make it better?"

The open-source ecosystem in OR is vast. The points below focus on the area I know best, which is optimization solver.

As a user

  • Give credit. This can be as simple as giving a "star" on GitHub or citing the paper/software in academic publications. Academic performance is driven primarily by paper citations, and researchers must show impact to secure funding.
  • Report bugs and hard instances. Bugs can't be fixed if they go unreported. When you do report a bug, try to include a working example that someone can copy-paste to reproduce the error. Hard instances help identify where there is room for improvement (both code-wise ans math-wise), and will drive future performance.
  • Help fund the development. This can take the form of donations (e.g. via NumFocus), paid-for support (when that's an possibility) or collaborative research. Plus, it's easier to tweak the software to fit your need when you have a hand in the development.

As a developer:

  • Make it easy to use. As a user, ease of installation is the first (time-wise) barrier to using software. One success story I can share is the way the Julia community has streamlined using open-source sovlers. Want to use Clp? just type "add Clp" and you're good to go. It's a godsend.

    Nowadays, there exists many tools to host, test and distribute software, manage dependencies, all across multiple platforms/architectures/languages, etc.

  • Provide documentation. It's tedious, it's annoying, you won't get promoted to full professor for doing it, but good documentation is a vital must-have. Similarly, there are tools to automate this, especially the rendering and hosting it online.

    It's also much easier for someone to contribute something if they can have access to good documentation, instead of having to figure out what each piece of code actually does and why.

  • Interface with modeling languages. More and more users only use solvers through a modeling language, e.g., JuMP, Pyomo, Gravity, etc. or commercial alternatives like AMPL and GAMS. Anything that has a C interface can be interfaced to all the open-source tools above, which then makes it much easier to gain users. It also removes the need to develop your own comprehensive interface, thereby freeing up time for other things.

  • Make it numerically robust. There's nothing worse than waiting a couple hours to see a solver crash due to numerical errors. IMO, a key to adoption is when users can trust that the solver will return a valid solution, without crashing or throwing an error, even if it means having to wait a little more.

$\endgroup$
3
  • 6
    $\begingroup$ I agree 100% with Answer 2. $\endgroup$
    – Kuifje
    Jan 6 at 10:01
  • 1
    $\begingroup$ Appreciate the "How to make it better" edit. If I could give a second upvote I would. $\endgroup$ Jan 13 at 5:29
  • $\begingroup$ I thought about creating a second answer :) there's a lot more that comes to mind. I tried to focus on what I found the most actionable at an individual level $\endgroup$
    – mtanneau
    Jan 13 at 14:43
17
$\begingroup$

Disclaimer: although I work for Gurobi, the views in this post are entirely my own.


I believe there are a few reasons for this trend:

  • First of all, the industries were "born" in different times. Bob Bixby founded CPLEX in 1988 (or thereabouts), while PyTorch was first released in 2016.
  • This also means though that these two industries are in different life cycles. The OR industry (especially around LP/MIP) has very much consolidated itself over the past 20-30 years, resulting in the situation we see today: a few commercial solvers which provide by far the best performance. This was not always the case: for example, when the bonmin package came out in the mid 00s, it was in quite a few cases better than the then state-of-the-art CPLEX. On the other hand, ML software is still evolving, with new methods and paradigms springing up at every conference (it seems at least). It will be interesting to see where the industry will be in 10-20 years, when a lot of the dust will have settled.
  • Finally, related to the life cycle point is also a point around performance: the code of commercial solvers is brutally performant. To achieve this level, you cannot have too many "cooks in the kitchen". How will TensorFlow or PyTorch achieve this performance, and is there even such a thing as a competitive performance benchmark (same training set, same algorithm types etc.) in the ML world?
  • However, even in the OR world you have a lot of open-source activity, especially around non-linear optimization. Since academics get e.g. Gurobi for free, many of them use it as their LP/MIP solver and then solver very complex non-linear or stochastic programming models. Check out for example the GitHub repo of Ruth Misener's group out of Imperial. This is fantastic work, all open-source and really cutting-edge in a lot of cases.
$\endgroup$
16
$\begingroup$

Update:

Since you updated your question might as well chip in, since I've worked with COIN-OR software a lot at the code level. In my experience, a lot of the open-source optimisation codebases (e.g. CBC) succeed in being amazing solvers, but fail in being great open-source projects. The heart of any successful open-source project (and by "successful" I mean one where many people decide to contribute) is the readability and design of its codebase, not the performance of the software per se. This is because readability and good design empower contributors to believe that they can improve things a lot, if they try long enough. What you want in an open-source project is a design where people can jump right in and start doing little things. If they need to spend months/years understanding what's happening before they can get their hands dirty, they will simply pass.

From a solver developer's point of view, the foremost reason is because a lot of these projects use autotools instead of CMake as a build system. Although it might not seem like much, it is unfortunately a deal breaker. The reason is quite simple. If we take CBC as an example, it is basically one massive file of code with lots of dependencies. This is very hard to read, let alone improve, even for a person like myself who does this for a living. What I could do, if the project were built with CMake, would be to slowly refactor the code, split it into many files and classes and improve encapsulation, so that it becomes much easier to read, understand, maintain, and improve over time, not just for myself but for other people. Of course someone could argue that I could do the same thing with autotools, but the simple truth of the matter is that people just don't use autotools anymore. I would need to spend months doing that full-time, which is time I simply don't have. It would be trivial however to make tiny changes over time if the project would build with CMake.

Therefore, this would be my recommendation: migrate the projects to CMake so that many more developers are able to contribute to the open-source code bases.

This is not pure conjecture btw. Even though CBC/CLP have been around for 20 years, HIGHS already has many more contributors despite being much younger. From a developer's point of view this makes perfect sense. The code is much more readable, and the project is built with CMake. This makes a massive difference. As another fun fact, building & linking CLP/CBC to our solver took a few weeks back in the day, especially since we also had to do it for Windows. Doing the same thing for HIGHS took 2 days - 1 days to link & build, and 1 day to test.

Original answer:

As an MINLP solver developer I'd like to share my experience on just how we make our solvers faster and why that's hard to replicate in an open-source environment.

Our day-to-day work revolves around meticulously running problems over and over again, analysing just what is happening, and thinking about how we can improve things:

  • We constantly find and eliminate code-level bottlenecks.
  • We reason how to skip calculations that are not necessary. This is typically math-specific, i.e., if my problem has some particular structure, do I really have to execute this piece of code?
  • Once we've ran out of code-level improvements, we go back to the math and try to identify and exploit special structure. Elucidating special structure often requires spending significant time to code new features into the solver.
  • Sometimes we find that our solver's architecture is limiting us, i.e., we actually can't code what we want at high performance because of certain design choices in the code. If we spot that enough times, we'll take the time (potentially many months) to rearchitect the entire code-base.
  • We'll meticulously run benchmarks on thousands of problems and tweak tolerances, parameters, working limits, and all sorts of little things to squeeze out more performance for a handful of problems, without regressing in performance for the remaining 10,000 ones. Doing this over many years stacks, and performance is improved by many times.
  • When nothing else works, we'll spend the time to figure out new algorithms, often for only a handful of problems.
  • When we break certain performance milestones, e.g., when our solver is now 100 times faster than it was 2 years ago, we go back and re-examine whether the new performance opens up new algorithmic options that were impossible a few years ago. At this point, we rinse and repeat the entire process.

This is what it takes to make a solver performant. Patience, knowledge, and meticulous work that is often unrewarding for long periods of time, until we get it to work.

There is a stark difference here between what we need to do and what ML developers need to do. In ML code, it's much more about an overall architecture that provides high throughput, and good APIs that provide users expressive freedom to create their algorithms. It is much less about manually running things and correlating performance to specific user input. This is why new ML frameworks keep popping up: once an ML framework is architected, the only way to really improve it is to design a new one. At its core, this is a difference in culture. ML users are often comfortable tweaking/designing their own algorithms, whereas solver users expect it to just work out of the box.

In light of the above, you might see how it's difficult for this process to happen in an open-source setting. Improving performance is not often not about doing something new and exciting. It's about taking a very long time to run the same thing over and over again until we figure out small tweaks that make that one problem 100 times faster without regressing in performance anywhere else. Even though I personally find that very satisfying, most people find it boring because they're not doing something "new". More importantly, in an academic setting, the bulk of this work isn't really publication-worthy - people can't really write a paper about how they spent 100 hours to figure out that changing an internal tolerance from 1.e-5 to 3.45e-5 resulted in solving 5 extra problems in the test set. In case you are wondering why this is the case, unfortunately these little things are nearly always implementation specific, i.e., they work in our own solver because of how the different systems chaotically interact with each other, but they are not transferable to any other solver.

Fun fact: just last week I figured out how to solve a problem I've been trying to solve for the last 2 years. During that time, I was working on that problem for a few minutes nearly every day, making tiny improvements once in a while. These improvements stacked, to the point where the very last improvement reduced the solving time from about 100 hours down to 700s on 8 cores. Even though I will admit to doing a little dance afterwards, I can't for the life of me tell you exactly why we can now solve this, as it's literally hundreds of little things over 2 years, let alone write a paper. This is very different from the ML community - if someone cracks an unsolved ML problem it will break the news the day after, simply because it's much more widely applicable. I do not consider that a bad thing, but you might see how ML would attract many more talented people, since the time/reward ratio is simply intrinsically better. This difference in the number of talented people working on the problem is, at the end of the day, one of the prime reasons for the differences we observe.

$\endgroup$
1
  • $\begingroup$ CMake is indeed a good point. It enabled much more convenient installation packages for the SCIP Optimization Suite (scipopt.org) and made compilation on Windows and macOS less stressful. It's still a pretty complicated build system but beats raw Makefiles any day. $\endgroup$
    – mattmilten
    Jan 12 at 14:26
12
$\begingroup$

Disclaimer: I do work for Fico/Xpress, one of the leading commercial optimization solver developers, but this is my own personal opinion.

I agree 100% with the comment about where the value is: the model or the algorithms. In ML the value is in the data/mode/computing power, in OR it is more in the algorithms.

About cultural differences: if you are an academic writing a paper in ML you are expected to show computational results. In OR you can publish papers that are technically correct, but nobody knows if the method is worth implementing, because the author didn't do it and the journal/editor didn't make them to. All we know is that the method is correct and it converges. I'm happy to see though that this attitude has been changing recently, and more and more OR journals require computational results before an article is published.

Personal side note on cultural differences: back in my academic days I once interviewed for a faculty position at an industrial engineering department, where I was told that it was not possible to get tenure for software work. Regardless of how much theoretical work went into the software or how useful it was in solving practical problems. That is not very encouraging for young faculty members hoping to do computational OR work in academia.

$\endgroup$
3
$\begingroup$

It seems to me like there are three worlds in OR:

  • users of commercial MIP/LP solvers like Cplex or Gurobi
  • users of free / open-source MIP/LP solvers
  • users of other type of solvers - constraint solvers, sat solvers ...

I'm in third group since I focus on constraint solvers, and help choco solver and or-tools solvers to be better. Without source codes it would be much harder, solvers can be without my bit of contribution little bit worse and performance of my optimization problems much worse.

Of course I'd like to not ignore MIP/LP solvers but it's hard to give a reason to pay high price of commercial solver only for experiments or small part of a solution.

From performance view, so far fantastic support of solvers that I use (choco solver, or-tools) and access to source codes allows me to be competitive with solutions that use commercial solvers.

For MIP/LP there should be some competitive alternative to commercial solvers that should be later preferred in academic world. It seems that a lot of knowledge is in IBM, Gurobi or Mosek and only way to have access to it is to be their employee. Without competitive open-source MIP/LP solver, other type of solvers can be in long run first choice and even gurobi (or cplex) ignored.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.