Repository navigation
SatParameter for deterministic time per batch #5199
Description
Activity
the real issue is that for some code, the correlation between time and dtime is bad.
Can you send us your model and the parameters you use to run it ?
Sadly I ran into this behavior on a model that I cannot share due to confidentiality. I'll do a sweep over our shareable instances to see if any of them trigger it (though I am not very optimistic) and attach one here if I find any.
Reacted by Mizux SeihaI haven't been able to isolate a shareable instance yet, but I'd still find a knob like this useful as a mitigation. We occasionally encounter this class of issue (much less often these days, I appreciate all the work that went into this), and if it persists we'll likely carry a local patch for a similar control while investigating the root cause. Having an officially supported option upstream would be preferable.
I can normally share most of our benchmarks and test cases. This particular instance just happens to be one I can't share publicly. If I manage to extract a representative reproducer, I'll gladly provide it. I think it's fine if we close it, and I can refile another ticket if I find a shareable instance later on.
Whether you decide to pursue this or close the issue, I mainly wanted to share the user perspective on why such a knob would be valuable.
What language and solver does this apply to?
CP-SAT,
interleave_search: trueDescribe 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_lpchunks 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_searchsensitive to subsolvers where the hardcodedmax_deterministic_time = 1.0chunk 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
SatParametersfield, for example: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.