Hacker News new | past | comments | ask | show | jobs | submit login

The history of state-of-the-art MIP solvers is fascinating. There are very few people in the world who can develop them, and there is a strong history of developers jumping ship from one company to another, tilting performance accordingly.

Initially, CPLEX and Xpress were founded in the eighties. In the nineties, CPLEX was acquired by ILOG (a French CP company), which in turn was purchased by IBM around 2009. Around the same time, the original technical co-founder of CPLEX, along with the two latest head developers, left CPLEX to found Gurobi. Since then, there has been a slow trickle of developers leaving CPLEX for Gurobi... until 2020, when CPLEX suddenly lost its 7 remaining devs over 6 months (because of catastrophic mismanagement at IBM, from what I heard). Unsurprisingly, those devs ended up mostly at Gurobi, resulting in the CPLEX team from 20 years ago being essentially Gurobi now. Other CPLEX devs also ended up at XPRESS, which had been purchased around 2008 by FICO (the credit rating company).

Meanwhile, there is also a smaller Danish company, Mosek, that does its own thing (they have a MIP solver, but their focus seems to be on their amazing conic optimization code). And SAS (the analytics giant) has a small MIP team too.

Then over the last 2 years, three new solvers appeared out of China: COPT (by Cardinal Operations, a startup by Stanford graduates), MindOpt (Alibaba Research) and OptVerse (Huawei). They mostly have LP solvers for now, but for newcomers, the performance is extremely impressive. This is only partially out of nowhere, though: COPT in particular has hired several devs from the incumbents.

On the academic side, ZIB (a PhD-granting research institute in Berlin) maintains a source-available family of solvers, and has been a steady provider of talent for commercial solvers. The dev behind SoPlex (LP solver) went to CPLEX after his PhD and now Gurobi. The main dev behind SCIP did the same, and is now VP of R&D at Gurobi. Many more XPRESS and Gurobi people did their PhDs at ZIB.

The Coin-OR open-source codes for LP (clp) and MIP (cbc) were written decades ago by a founding father of computational optimization, John Forrest, now retired from IBM research. Their source code is difficult to read, and Coin-OR aims to eventually replace them with a new code, HiGHS. The dev who wrote the simplex code of HiGHS as his PhD thesis went on to XPRESS and now COPT. The dev who writes the MIP code of HiGHS comes from ZIB.

As you can see, everyone is very inter-connected. Hence the throwaway :-).




If you're interested in the performance state-of-the-art for optimization solvers, the reference is Hans Mittelmann's regularly updated benchmarks [1]. They sometimes get criticized by solver makers (because one could easily game the benchmarks), but:

1. At least they exist! They give a good rough idea of the relative performance of the various solvers. Also, I think it provides a sense of competition that is great for innovation. Some of the newcomers push press releases about having "won a prize" when they leapfrog the competition in one of the (sometimes weekly) benchmarks.

2. For the MIP benchmarks [2], a lot of thought has gone into doing them properly [3].

Don't be scared by the "End of a benchmarking era" banner. In 2018, Gurobi cherry-picked numbers that made them look good in some promotional material, while suggesting endorsement by Hans Mittelmann. There was a whole fuss about it and they had to publicly apologize [4]. This was a very dumb move since they were the fastest solver anyways, just not by as much as they claimed. CPLEX and Xpress took this as an excuse to take their toys and go home (they have since refused to participate in benchmarking). Gurobi was banned from the benchmarks for a while, but now they're back.

[1] http://plato.asu.edu/bench.html

[2] http://plato.asu.edu/ftp/milp.html

[3] https://link.springer.com/article/10.1007/s12532-020-00194-3

[4] https://web.archive.org/web/20181224083542/http://www.gurobi...


Thanks! I didn't know that the benchmarking had resumed. Good news. I hope CPLEX and Xpress return someday.


you could also write a similar story about the predatory licensing of cplex and gurobi. when gurobi started their model was "we're the opposite of cplex, and we don't count cores". but they realized that wasn't making them enough money.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: