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.

I recently ran across a paper comparing Constraint Programming (CP) and Mixed-Integer Programming (MIP) for scheduling operating theatres (if you don’t have access, here is what appears to be an earlier version).

I went googling for some other comparisons. Here’s what I found:

• Comparing Solution Methods for the Machine Reassignment Problem (2012): “The results suggest that our CP-based LNS can scale to large instances and is superior in memory use and the quality of solutions that can be found in limited time.”
• CP and MIP Methods for Ship Scheduling with Time-Varying Draft (2012): “We found that the CP model with a good choice of search strategy was significantly faster and was able to solve larger problems than the MIP model.”
• Comparing Mixed & Integer Programming vs. Constraint Programming by solving Job-Shop Scheduling Problems (2015): “In this work, each model is individually analyzed and then compared considering: i) Optimization success performance, ii) Computational processing time, iii) Greatest Resource Utilization and, iv) Minimum Work-in-process Inventory. Results demonstrated that CP-2 presented best results on criteria i and ii, but MIP was superior on criteria iii and iv and those findings are discussed at the final section of this work.”
• A comparison of an CP and MIP approach for scheduling jobs in production areas with time constraints and uncertainties (2018): “The test results show that the CP model outperforms the MIP and quickly finds much earlier usable schedules for large problem sizes.”
• A Comparison of Constraint Programming and Mixed‐Integer Programming for Automated Test‐Form Generation (2018): “Both examples show that CP works well with feasible solutions and running times likely to be better than that for MIP‐based applications.”
• An Update on the Comparison of MIP, CP and Hybrid Approaches for Mixed Resource Allocation and Scheduling (2018): “We consider a well known resource allocation and scheduling problem for which different approaches like mixed-integer programming (MIP), constraint programming (CP), constraint integer programming (CIP), logic-based Benders decompositions (LBBD) and SAT-modulo theories (SMT) have been proposed and experimentally compared in the last decade. Thanks to the recent improvements in CP Optimizer, a commercial CP solver for solving generic scheduling problems, we show that a standalone tiny CP model can out-perform all previous approaches and close all the 335 instances of the benchmark.”

Perhaps Google knows I have a CP bias. 🙂 Or perhaps someone can point to alternative results in the Comments.