SAT Presolve time limit

[ianbenlolo]

Hey,

I was wondering if there is any way to set a limit on the presolve time. I have a model that usually solves in a few minutes but rarely i see inputs where the model crashes due to the presolve taking up the whole timelimit. Is there any way to set a time limit on the presolve stage? I see i can disable it entirely with solver.parameters,cp_model_presolve=False but I don't know if that is recommended.

I am using python with ortools 9.9.3963.

Thanks in advance!

[sschnug]

Some opinions from another ortools "user":

General: presolve vs. solve/search:

In general i would assume, that presolving is more cost-efficient than real search.

This implies, that there are probably not that many cases (aka outliers), where limiting presolve helps when being evaluated over the whole search/solve itself (time to first feas-sol; time to incumbent of value X).

But maybe you found one of those.

Presolve outliers:

That being said, sometimes some automatic presolve settings CAN hurt, especially (i'm mostly going by algorithms not necessarily linked to ortools' implementation; e.g. alternative MILP solvers):

• symmetry-detection
• probing
• clique-merging

Presolve limits in CP-SAT:

Quickly skimming over or-tools/ortools/sat/sat_parameters.proto i did not find an easy max_time_presolve, but many more specific presolve-control parameters.

I guess it would be a good idea to identify the "problematic" candidates (logs?) or deduce them by trial-and-error / experimentation with these settings.

The good thing is, that there are some mechanisms for control linked to what i would look out for (the ones mentioned before).

For example:

Section Presolve

optional double probing_deterministic_time_limit = 226 [default = 1.0];
optional double presolve_probing_deterministic_time_limit = 57 [default = 30.0];

optional int32 max_presolve_iterations = 138 [default = 3];

optional int32 cp_model_probing_level = 110 [default = 2];

optional double merge_no_overlap_work_limit = 145 [default = 1e12];
optional double merge_at_most_one_work_limit = 146 [default = 1e8];

optional int64 presolve_inclusion_work_limit = 201 [default = 100000000];

Inprocessing

As inprocessing is basically presolve during search, you might need to also touch those. But i would delay this (until needed).

Other

optional int32 symmetry_level = 183 [default = 2];

Summary

While there might be no easy / ergonomic time-limit control, there is a more explicit mechanism of control (arguably more powerful in many cases), although a bit more cumbersome.

I'm pretty optimistic, that you will be able to find and "tune" whatever makes your problem slow given the options here!

[ianbenlolo]

Thank you for the writeup it is very helpful 😃!
I did find some of those params before but was weary of messing with them. I suppose I will try to find a good combination of them with some trial and error. I think it was stalling on the second presolve iteration (at [MaxClique] Merged 6608(13216 literals) into 6272(12544 literals) at_most_ones.) so setting max_presolve_iterations=1 might be my solution.

This will probably hurt many cases however which is why I wanted to set a more general timelimit for presolve.
I will fiddle with the other params to see if there may be a better way though!

Thank you!

[jmarca]

Thanks for posting this excellent writeup!JamesOn Jun 21, 2024, at 15:30, sschnug ***@***.***> wrote: Some opinions from another ortools "user": General: presolve vs. solve/search: In general i would assume, that presolving is more cost-efficient than real search. This implies, that there are probably not that many cases (aka outliers), where limiting presolve helps when being evaluated over the whole search/solve itself (time to first feas-sol; time to incumbent of value X). But maybe you found one of those. Presolve outliers: That being said, sometimes some automatic presolve settings CAN hurt, especially (i'm mostly going by algorithms not necessarily linked to ortools' implementation; e.g. alternative MILP solvers): symmetry-detection probing clique-merging Presolve limits in CP-SAT: Quickly skimming over or-tools/ortools/sat/sat_parameters.proto i did not find an easy max_time_presolve, but many more specific presolve-control parameters. I guess it would be a good idea to identify the "problematic" candidates (logs?) or deduce them by trial-and-error / experimentation with these settings. The good thing is, that there are some mechanisms for control linked to what i would look out for (the ones mentioned before). For example: Section Presolve optional double probing_deterministic_time_limit = 226 [default = 1.0]; optional double presolve_probing_deterministic_time_limit = 57 [default = 30.0]; optional int32 max_presolve_iterations = 138 [default = 3]; optional int32 cp_model_probing_level = 110 [default = 2]; optional double merge_no_overlap_work_limit = 145 [default = 1e12]; optional double merge_at_most_one_work_limit = 146 [default = 1e8]; optional int64 presolve_inclusion_work_limit = 201 [default = 100000000]; Inprocessing As inprocessing is basically presolve during search, you might need to also touch those. But i would delay this (until needed). Other optional int32 symmetry_level = 183 [default = 2]; Summary While there might be no easy / ergonomic time-limit control, there is a more explicit mechanism of control (arguably more powerful in many cases), although a bit more cumbersome. I'm pretty optimistic, that you will be able to find and "tune" whatever makes your problem slow given the options here! —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>