Performance regression from v9.7 -> v9.8-v9.11

**What version of OR-Tools and what language are you using?**
Version: v9.7, v9.8, v9.9, v9.10, v9.11
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](https://github.com/slothy-optimizer/slothy).

**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](https://github.com/google/or-tools/files/14817531/model.txt) (5.4MB) and the following as `run_model.py`:

```python
# 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)
```
2. In an environment with OR-Tools v9.7/v9.8/v9.9 setup, do
```bash
python3 run_model.py
```
3. 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):

```bash
[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](https://github.com/slothy-optimizer/slothy/pull/47)) or v9.9 ([PR](https://github.com/slothy-optimizer/slothy/pull/46)) in [SLOTHY](https://github.com/slothy-optimizer/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.