A brief look at Google vs IBM: A Constraint Solving Challenge on the Job-Shop Scheduling Problem from ICLP 2019.

The Abstract:

“The job-shop scheduling is one of the most studied optimization problems from the dawn of computer era to the present day. Its combinatorial nature makes it easily expressible as a constraint satisfac- tion problem. In this paper, we compare the performance of two constraint solvers on the job-shop scheduling problem. The solvers in question are: OR-Tools, an open-source solver developed by Google and winner of the last MiniZinc Challenge, and CP Optimizer, a proprietary IBM constraint solver targeted at industrial scheduling problems. The comparison is based on the goodness of the solutions found and the time required to solve the problem instances. First, we target the classic benchmarks from the literature, then we carry out the comparison on a benchmark that was created with known optimal solutions, with sizes comparable to real-world industrial problems.”

From the Conclusion:

“Concluding, CP Optimizer performed slightly better than OR-Tools on the classic benchmark, but was absolutely superior on the large-scale one. In fact, CP Optimizer was able to optimally solve 66% of the large-scale instances, against 29% of OR-Tools (quad core). By exploiting multi cores, OR-Tools was also able to find optimal solutions for the large-scale instances, showing that nowadays CP solvers in general could be successfully applied to real-world industrial problems.”

Old ILOGers — full disclosure I once served on ILOG’s Technical Advisory Board 🙂 will be pleased. And we should all be pleased at the conclusion “showing that nowadays CP solvers in general could be successfully applied to real-world industrial problems”. Of course, CP has been successfully applied in many real-world domains for many years.