or-tools: Performance regression from v9.7 -> v9.8/v9.9

What version of OR-Tools and what language are you using? Version: v9.7, v9.8, v9.9 Language: Python

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)

CP-SAT

What operating system (Linux, Windows, …) and version?

Apple M1 Pro, MacOS Sonoma Version 14.3.1

What did you do?

Updated OR-Tools from v9.7 to v9.8 and v9.9 when used as the backend for the SLOTHY assembly superoptimizer.

What did you expect to see

CP-SAT performance that is similar or better in terms of runtime and consistency.

What did you see instead?

Significant inconsistency in the runtime of CP-SAT.

Steps to reproduce:

1. Save the attached model.txt (5.4MB) and the following as run_model.py:

# Following https://groups.google.com/g/or-tools-discuss/c/jg-LYSWAgZA/m/QMsyJQI-AgAJ

import ortools
from ortools.sat.python import cp_model
from google.protobuf import text_format

TIMEOUT=15 # In the good case, the model solves in ~8s on an Apple M1
ITERATIONS=30

def load_and_solve(i):
    model = cp_model.CpModel()
    with open("model.txt", "r") as file:
        text_format.Parse(file.read(), model.Proto())
    print (f"[{i}]: Solve using OR-Tools v{ortools.__version__} ... ", end='', flush=True)
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = TIMEOUT
    status = solver.Solve(model)
    status_str = solver.StatusName(status)
    print(f"{status_str}, wall time: {solver.WallTime():.4f} s")

for i in range(ITERATIONS):
    load_and_solve(i)

1. In an environment with OR-Tools v9.7/v9.8/v9.9 setup, do

python3 run_model.py

1. Observe
   • High consistency in performance for v9.7
   • Low consistency in performance for v9.8 and v9.9

Here are the outputs on my local machine (see above):

[0]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.7095 s
[1]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6358 s
[2]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6029 s
[3]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6173 s
[4]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6677 s
[5]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6342 s
[6]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6091 s
[7]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6222 s
[8]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6853 s
[9]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6149 s
[10]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6368 s
[11]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6400 s
[12]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6311 s
[13]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6256 s
[14]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6580 s
[15]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6790 s
[16]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.5866 s
[17]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6641 s
[18]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6367 s
[19]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.5504 s
[20]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6438 s
[21]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6866 s
[22]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6646 s
[23]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6997 s
[24]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.7523 s
[25]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6659 s
[26]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6842 s
[27]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6527 s
[28]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6678 s
[29]: Solve using OR-Tools v9.7.2996 ... OPTIMAL, wall time: 7.6791 s

[0]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0477 s
[1]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0498 s
[2]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 8.0398 s
[3]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0509 s
[4]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0495 s
[5]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 7.7925 s
[6]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0494 s
[7]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0490 s
[8]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0499 s
[9]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0521 s
[10]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0441 s
[11]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 7.5001 s
[12]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0480 s
[13]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 7.7570 s
[14]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0510 s
[15]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0435 s
[16]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0512 s
[17]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0548 s
[18]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0482 s
[19]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0505 s
[20]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 7.7389 s
[21]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0518 s
[22]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0549 s
[23]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0517 s
[24]: Solve using OR-Tools v9.8.3296 ... OPTIMAL, wall time: 8.5971 s
[25]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0511 s
[26]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0454 s
[27]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0479 s
[28]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0486 s
[29]: Solve using OR-Tools v9.8.3296 ... UNKNOWN, wall time: 15.0584 s

[0]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.5733 s
[1]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1111 s
[2]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1614 s
[3]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 8.0639 s
[4]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 8.1368 s
[5]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9110 s
[6]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1061 s
[7]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1078 s
[8]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1067 s
[9]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9369 s
[10]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 8.0701 s
[11]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9486 s
[12]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9123 s
[13]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1139 s
[14]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1011 s
[15]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.5487 s
[16]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9708 s
[17]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1062 s
[18]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1557 s
[19]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1104 s
[20]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1042 s
[21]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1049 s
[22]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9224 s
[23]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 8.0476 s
[24]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1151 s
[25]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9463 s
[26]: Solve using OR-Tools v9.9.3963 ... UNKNOWN, wall time: 15.1065 s
[27]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9260 s
[28]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9473 s
[29]: Solve using OR-Tools v9.9.3963 ... OPTIMAL, wall time: 7.9736 s

Anything else we should know about your project / environment

• The issue was observed when trying to update OR-Tools from v9.7 to v9.8 (PR) or v9.9 (PR) in SLOTHY, which led to CI failing because of timeouts.
• The model provided here is representative of what seems to be a general slowdown / increase of performance variability of CP-SAT for the kinds of models generated by SLOTHY. It can be generated as logs/ntt_dilithium_45678_a55_model.txt via python3 example.py --examples ntt_dilithium_45678_a55 --log-model based off the SLOTHY main branch.
• Thank you for your work! CP-SAT has so far worked amazingly well as SLOTHY’s backend.

If you need any more information, please let me know.