google / google/or-tools

SatParameter for deterministic time per batch

Open
#5,199 3 comments 0 reactions 1 assignee Claimed by @lperron View on GitHub
Solver: CP-SAT Solver
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

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.