SatParameter for deterministic time per batch
- Dominant language
- C++
- Stars
- 14.1k
- Forks
- 2.5k
- Avg merge
- 8h 39m
- Merged PRs (30d)
- 72
Description
**What language and solver does this apply to?**
CP-SAT, `interleave_search: true`
**Describe the problem you are trying to solve.**
On some large CP-SAT instances, interleaved search can run only a small number of batches because individual full-problem subsolver chunks take a very long wall-clock time.
In one case, several quick_restart variants found feasible solutions around 100s, but total wall time was about 600s. The task timing table showed `no_lp` chunks taking several minutes of wall time each. Because the interleaved batch does not appear to synchronize until the selected subsolvers finish their chunks, the useful solutions were not reported until much later.
This makes `interleave_search` sensitive to subsolvers where the hardcoded `max_deterministic_time = 1.0` chunk corresponds to a large wall-clock duration.
**Describe the solution you'd like**
Expose the deterministic-time limit currently hardcoded for full-problem interleaved subsolver chunks as a `SatParameters` field, for example:
```protobuf
interleave_search_full_problem_dtime: 1.0
```
The default could remain 1.0, preserving current behavior. Users with large or uneven instances could tune it lower, e.g. 0.2 or 0.5, to force more frequent synchronization between subsolvers.
**Describe alternatives you've considered**
I tried changing interleave_batch_size, but it did not solve the issue by itself. With interleave_batch_size: 2 and a lower chunk deterministic-time limit that I quickly implemented on my end (just a few lines of code), chunks became much shorter and more batches ran, but this is not currently tunable without modifying OR-Tools source.
**Additional context**
I understand that this could have unintended consequences if a user tunes it to be too low, however I think it would be very useful to expose a knob for the users to experiment with.
Contributor guide
Assessment
This issue has not been assessed yet.