google / google/or-tools

uninterruptible PresolveCpModel() can become effectively stalled when called from variables_shaving subsolvers, with large model

Open
#5,163 13 comments 0 reactions 1 assignee Claimed by @lperron View on GitHub
Bug Solver: CP-SAT Solver
Dominant language
C++
Stars
14.1k
Forks
2.5k
Avg merge
8h 39m
Merged PRs (30d)
72

Description

**What version of OR-Tools and what language are you using?**
Version: 9.15.6755
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?**
Ubuntu 24.04.3 LTS

**What did you do?**
I ran a particular CP-SAT model (1.1M+ variables) from python, allowing 64 workers.

**What did you expect to see**
Based on the logs, it seems that the optimum was identified and proven optimal in under 600 seconds. Ideally, the solver would terminate shortly after this point.

**What did you see instead?**
The solver continues on for another ~1.5 hours before returning result, apparently related to the three `variables_shaving` subsolvers. (Note: The issue is more obvious if I specify `solver.parameters.max_time_in_seconds = 600.0`. The time limit is not respected and the solver continues on for an additional ~1.5 hours.)

I've attached the full log, which includes the task timing details.

[CP-SAT.variables_shaving.performance_issue.txt](https://github.com/user-attachments/files/27688001/CP-SAT.variables_shaving.performance_issue.txt)

**Anything else we should know about your project / environment**
I suspect my model is so large that individual calls to [CopyModelConnectedToVar()](https://github.com/google/or-tools/blob/79e340fd50e1cae499bd6c9035486cf06c8261a5/ortools/sat/shaving_solver.cc#L498) could be taking a significant amount of time. That function doesn't currently seem to include any checks to `shared_->SearchIsDone()` or `shared_->time_limit->LimitReached()`, so I think it may effectively become a "zombie process". (Perhaps checks for completed-search / time-limit-reached would be appropriate, maybe around [L518-519](https://github.com/google/or-tools/blob/79e340fd50e1cae499bd6c9035486cf06c8261a5/ortools/sat/shaving_solver.cc#L519)?)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.