18
$\begingroup$

I come from an ML background, and occasionally have to dive into the OR world. I am trying to figure out whether I need to purchase a commercial solver license for a certain problem set.

In the ML world, open source libraries like Tensorflow, Scikit-Learn, PyTorch, etc...are as good as it gets in terms of performance and features. Whether to go with open source or commercial product is more a Human Resources consideration: Do you have an ML engineering team capable of building and deploying models with open source libraries? If so, going with a commercial product makes no sense whatsoever.

Is the situation similar with OR solvers? Or are there more in-depth reasons that justify paying the license for a commercial solver, e.g.: performance, size of search space, SLAs, quality of results, etc...?

$\endgroup$
2
  • 4
    $\begingroup$ Commercial solvers are usually better, see or.stackexchange.com/questions/892/… $\endgroup$ – Stradivari Nov 4 '20 at 21:48
  • 1
    $\begingroup$ I vote up your interesting question but, you actually could have asked, "what are the disadvantages of commercial solver other than license payment over the open-source solvers?". Obviously, with a team of dedicated researchers and programers (that means monthly salary for the company to pay), commercial solvers are performing better than the open-sources in any term. (sorry for personal opinion) $\endgroup$ – Oguz Toragay Nov 6 '20 at 21:50
34
$\begingroup$

Disclaimer: I am currently working for a commercial solver company (Gurobi) and have worked before on another commercial solver (IBM CPLEX). Hence, my opinion may be biased, but still I am trying to not turn my answer into a marketing and sales pitch. For my PhD thesis I developed the academic solver SCIP, which is still actively maintained and developed by a large group of researchers, so I also know the academic side of the solver world. In any case, what I am going to say is my personal opinion and not necessarily aligned with my current or former employers or my former research group.

I agree with dhasson's points, but I would like to emphasize a certain aspect of performance (also addressed in Kuifje's answer) that I think is hard to understand in its full consequences for people that are not experts in operations research.

First, let me state that I am only discussing mixed integer programming (MIP) here, which is just a small sub-area in the field of operations research, but I think is the main topic that Skander H.'s question is about.

The main issue of performance for mixed integer programming solvers is that all known algorithms for MIP have exponential worst-case running time. While this may also be true for other areas like ML or data base operations, I think that in practice the algorithms that are applied there scale reasonably well with the size of the input data.

For MIP, the running time heavily depends on the structure of the model to be solved and on the capabilities of the solver to exploit this structure. If there is no useful structure in the model or if the solver is not able to identify and exploit the structure, then you will often see that the theoretical exponential growth in running time manifests itself in practice.

For example, there are models with just 50 binary variables and a handful of constraints that are pretty much unsolvable with today's state-of-the-art algorithms. And for such models each additional binary variable pretty much doubles the resulting runtime. You really can see the exponential complexity. On the other hand, there are models with millions of variables and constraints that can be routinely solved to optimality. This is true for both free/academic solvers as well as commercial solvers.

Fortunately, models of practical problems that are of interest in industrial applications are most often of the latter type. Nevertheless, as said before, being able to solve a model or not within reasonable time heavily depends on whether the solver at hand is able to identify and exploit the structure of the model. And this is where the main difference is between free/academic solvers and commercial solvers when it comes to performance. Commercial vendors with their teams of full-time developers and their large customer base who provide models from a diverse set of applications are just in a much better position to develop, implement, and tune algorithms to cover all these different aspects and structures that appear in real-world models. Hence, the likelihood that the solver deals nicely with your application type is larger if you select a commercial solver.

And this aspect does not show very well in the performance comparisons that you see in publicly available benchmarks. From the pictures like the one that Kuifje refered to, you may get the conclusion that free solvers are something like 5 or 10 or 20 times slower than the best commercial solvers. And then, you may think "speed is not that relevant for me, I don't mind having to wait 10 minutes instead of just 1 minute". But this is just not the right way of looking at this. Check also the number of models that could be solved to optimality: in the (relatively old) picture you can see that CBC (which is a good free solver) is able to solve only 48 out of the 87 problem instances, while the commercial ones solve 86 of them.

For your particular problem class, it could be that a free solver just behaves nicely and has the same or at least comparable performance than a commercial solver. It could even be that there is some research advancement implemented in the free/academic solver that has not yet found its way into the commercial product and thus the free solver is actually faster than the commercial product. But there are also a number of cases where the models for your problem class are intractable for one solver while they can be solved in a fraction of a second by a different solver, often a commercial one.

This is what I think is often hard to grasp. From, say, ML algorithms or data bases or operating systems or whatever type of software where you have both commercial and free (open source) alternatives, one is used to commercial products being maybe a little faster or a little better or just a little different in certain aspects. But there usually is not the difference between "it is impossible to solve my problem" versus "my problem solves very easily". But this is sometimes the case for MIP solvers.

Thus, I would recommend the following approach:

First, you consider all the various other aspects that have been mentioned above by dhasson. Is a reliable support, SLA, cloud computing, a certain API or platform support essential to you? What about the other non-standard features that some commercial solvers offer? Is there a free solver that provides what you need? If not, you are already bound to looking at commercial alternatives.

If a free solver is a valid option, then pick one based on publicly available benchmarks and try to solve your models with it. Just check if it works. Verify carefully whether the results are correct, because apart from performance there is also the aspect of numerical robustness that is often better in commercial products. Try multiple problem instances of your problem class. And if everything works well with the free solver, just stick to it for this project.

But if at some point you run into a wall, for example because the free solver is just unable to solve your problems, then please do not make the mistake of dismissing the whole technology of mixed integer programming. It could be that with the solver you tried it appears completely hopeless to solve your problem and you have the impression that you need to look at a completely different approach like implementing a heuristic. But at this point it is definitely time to check out commercial alternatives. The commercial vendors provide evaluation licenses such that you don't need to pay anything for a first try. And it can very well be that you are going to be positively surprised. It happens frequently that a commercial solver can solve certain types of models easily that appear completely hopeless with a free solver. And this is not only due to the differences in free and commercial products, it can also happen when switching from one free solver to another, or when comparing different commercial solvers. For example, it could very well be that Gurobi struggles for some problem class but CPLEX and XPRESS have no issue at all with it. So, please try different alternatives before you give up! MIP is really a cool and useful technology that is worth learning and embracing.

$\endgroup$
1
  • 4
    $\begingroup$ Nice post. You da man. $\endgroup$ – Mark L. Stone Nov 5 '20 at 16:27
17
$\begingroup$

No, the situation isn´t the same for OR libraries. There are several reasons for this, among them being

  • Performance: The difference is relevant, with an emphasis on Mixed Integer Programming (linear and nonlinear). For Linear Programming it's less abrupt but it still exists. You can see empirical results in e.g. the Mittelmann benchmarks for Optimization Software. As mentioned in the website, the current version doesn't contain some commercial solvers, but previous ones did and the results are still available online.

  • Size of search space: Yeah, first, in general commercial solvers have state of the art implementations with dedicated developer teams focused in scalability, high performance, robustness, multithreading, heuristics (e.g. feasibility pump) and other features which tend to make their software more capable of handling large search spaces, when compared to open source solvers. I'm not saying that open source solvers (e.g. CLP, CBC, DIP) are bad: they too have many of the same great tricks and advances in capabilities implemented. It just isn't the same you can achieve with a large funding agenda and teams dedicated full time to research and development. Second, for some specific problems where the search space is too large, it can be worth it(*) to design heuristics, apply metaheuristics, or other similar approaches which don't guarantee an optimal solution but can be validated on realistic instances to compare the solution with the optimum. Otherwise you could need sofisticated methods like decomposition methods which have their own numerical issues and some organizations tend to prefer simpler models for different reasons (**).

  • SLA is definitely an important factor. Sometimes open source code will have bugs - because of library-solver integration or even a numerical issue in the solver's code - and it's not the same to have immediate or fast support vs a project maintained by a couple of people who may not be able to dedicate full time. You could try solve the bugs yourself and contribute but it'll be difficult if your project (which uses the solver) needs to be shipped soon.

  • Quality of solution this can be related to the discussions above on performance, SLA and realiability.

  • Integration with other services and frameworks: Commercial solvers tend to have APIs available for a couple of programming languages, which can make it easier to integrate them into larger projects for organizations. Even more, some of them (e.g. Gurobi and CPLEX) have kept the rythm of the market and started adding cloud computing capabilities.

  • User experience, user base and adoption: Many times tere's a significant gap in quality of documentation, completeness of documentation,, ease of installation (can be excrutiatingly painful for many open source solvers, almost impossible in a Windows OS), availability of online resources/size of community (large open-source communities in ML, not the case for OR). Hopefully the adoption of OR methods will change in the future as part of the analytics community starts adopting optimization knowledge for prescriptive modeling. In many practical situations, making decisions is the end goal of predictive modeling, and optimization can help to make efficient decisions. And this can be combined with organizational constraints like budget, workforce hours, or infrastructure capacity. Some examples:

    1. demand prediction is an intermediate step for capacity allocation or production planning
    2. fraud and churn prediction must be followed by actual decisions (which campaign or action, how many resources to assign to each customer, and when)
    3. stockout predictions are not the end goal, planning when to replenish which SKU, and how much, should be
    4. Estimates of willingness to pay can be a first step towards revenue optimization.

Note that for continuous optimization, there are great solvers available in open source software. SciPy contains many of them (L-BFGS-B etc), CVX is centered on convex optimization, and OSQP for Quadratic Programming. But even in these cases, using commercial solvers (e.g. MOSEK and BARON) tends to be faster or achieve better solutions in a fixed same timeframe.

Also what makes choosing OR software more complex is that there's no free lunch, no universal ranking (in part because only internal teams know what their program does and how it works). There are cases where Gurobi is better than CPLEX for some model instance A while the reverse situation happens for a different instance B. A specific nonlinear solver could perform significantly better than Gurobi/CPLEX for a model you have in mind. And if this is important or not will depend on your available computing infrastructure. To add more complexity into this, it can happen that a Constraint Programming model for a specific problem is solved in seconds while a Mathematical Programming solver takes several minutes or hours to obtain a solution of similar quality, or viceversa.


(*) To delve into the reasons why I said for some specific problems where the search space is too large, it can be worth it, please refer to Tobias Achterberg's answer that covers the reason into more detail. With worth it I mean in terms of available budget for the solution vs the incremental savings/benefits it will bring. This isn't a hard constraint, as the OR practitioner's knowledge can help tweaking a software and changing the modelling approach to one that performs well.

(**) Might be practical reasons, as the model will likely need maintenance, tuning and/or updates in the future. If the solution was developed by consultants, it could be nontrivial to do these tasks by an internal team.

$\endgroup$
2
  • 2
    $\begingroup$ I would add quality of documentation (see Gurobi), ease of installation (excrutiatingly painful for many open source solvers), availability of online resources/size of community (large open-source communities in ML, not the case for OR). $\endgroup$ – ktnr Nov 5 '20 at 9:42
  • $\begingroup$ @ktnr yes, that's unquestionable. Forgot to include it, thanks. $\endgroup$ – dhasson Nov 5 '20 at 11:37
16
$\begingroup$

I think the short answer is: speed.

Most optimization problems solved in the OR world are computationally intractable, they cannot be solved in reasonable time as the size of the data increases. A commercial solver will allow you to push back the limit of the size of the problem you are tackling, and to solve the small ones very fast.

If you checkout for example Gurobi's benchmarks, you can see the big difference between open source and commercial solvers:

enter image description here

I have seen problems in the past where CBC (best open source solver) cannot find a feasible solution after more than 30 hours, and commercial solvers solve optimally within 15 minutes.

$\endgroup$
6
$\begingroup$

(Full disclosure: I run a solver company)

The state of the art

Unlike ML, in the optimisation space commercial software is unfortunately on average superior to open-source alternatives. This does not mean that open source can't be a perfectly viable choice. Open source solvers can and do solve very difficult problems. It just means that commercial solvers can solve many problems that are well beyond the scope of what we can expect open-source solvers to be able to solve.

The are many reasons why, but at the end of the day it comes down to the fact that optimisation solvers are solving a "more difficult" problem that ML frameworks do, and there are far fewer people who know how to write solvers well. Therefore, the necessary volume of developers to support viable open-source alternatives doesn't really exist yet.

ML is much closer to the curriculum of your average computer scientist, which is partially why we have so many good frameworks. In order to write a good optimisation solver the developer needs to also understand the math, and most CS curricula don't include higher math, so good hobbyists are much harder to come by.

Also don't forget that the main reason we have such good ML frameworks today is because big corporate money funded its development (e.g. Google). This hasn't happened in the optimisation space yet, nor does it seem likely to happen anytime soon.

The commercial perspective

When it comes to open source vs commercial there are numerous straightforward answers as to what differentiates commercial software: speed, robustness, plurality of interfaces, better user experience, and of course support. The more subtle answers (and in many ways the most crucial ones) are data bandwith and tuning.

At the end of the day though, it comes down to this: the better our solvers are, the more money we make. Therefore, we have incentive and resources to pour money and time towards constantly improving the solvers and the user experience. Open source relies on expert volunteers, and unfortunately, as I mentioned in the beginning of this, there are very few professional solver developers in the world to begin with.

Speed

The speed is quite intuitive and has been answered by other people, so I won't cover that. We're all pretty fast. Often >1000x faster than open source.

Robustness

Robustness is less obvious. If you run open source software enough, you will see quite a few bugs. Enough bugs in fact, that e.g. most COIN-OR software is hard to use in production. Commercial solvers have Q&A teams, plus thousands of customers' feedback and bug reports, so it makes sense that our software breaks less frequently.

Interfaces

This is also a trivial argument, solver companies will spend money to build and test good interfaces for numerous programming languages, GUIs, and modelling frameworks. In open source there's little incentive to do that.

Better user experience

Another intuitive one: the easier it is to use our software, the more customers we can get. With open-source solvers, devs seem to care more about the core functionality, not how easy it is for others to use. This makes sense - working on algorithms is fun and stimulating, debugging Python interfaces isn't.

Support

Often the main incentive to buy a solver, you know that if something goes wrong you're not on your own.

Tuning

Having teams of people working full-time to make the software faster, and also having seen thousands of real problems from customers, gives us resources not available to the open-source community to tune our solvers to run better on the most commonly encountered problems.

Data bandwidth

The elephant in the room. The other main reason to buy a commercial solver is that it's typically designed to process large amounts of data efficiently. Most solvers will instantly hit a ceiling when large problems are loaded because, even if their algorithms are great, their implementation doesn't scale beyond a certain data bandwidth. This is absolutely a ceiling for the vast majority of open-source solvers, and for many commercial solvers as well btw. Once you've worked with enough solvers you just know that if a problem is large-ish, there's no point even trying to load it on certain solvers. In Octeract Engine for instance, we have 4 classes of implementations for data structures and most expensive algorithms, and the solver switches between them dynamically depending on problem size: small, mid-size, large, and humongous. The only reason we got to do that though is because we had users who couldn't solve certain problems, which made us aware of the bottlenecks.

$\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.