max_time_in_seconds is not always adhered to

[S. K.]

I'm encountering two problems with the max_time_in_seconds parameter for the CP-SAT solver.

1) The solver is stopping after the presolve although there is still plenty of time left.

For example:

Starting CP-SAT solver v9.12.4544
Parameters: random_seed: 6 use_optimization_hints: true max_time_in_seconds: 500 log_search_progress: true num_search_workers: 12 max_presolve_iterations: 2 hint_conflict_limit: 75000 log_subsolver_statistics: false probing_deterministic_time_limit: 0.35 

Initial optimization model '': (model_fingerprint: 0xf7619c0c52edd203)
#Variables: 57'749 (#bools: 1'181 in objective)
  - 13'755 Booleans in [0,1]
  - 172 different domains in [-1,12285] with a largest complexity of 16.
  - 1 constants in {1}
#kBoolOr: 3'478 (#enforced: 3'324) (#literals: 3'478)
#kCircuit: 11
#kCumulative: 32 (#intervals: 8'757, #optional: 8'757, #variable_sizes: 8'757)
#kIntProd: 10'629
#kInterval: 11'768 (#enforced: 10'745) (#fixed: 1'022)
#kLinMax: 44 (#expressions: 188)
#kLinear1: 18'041 (#enforced: 17'934)
#kLinear2: 93'688 (#enforced: 93'687 #multi: 18'792)
#kLinear3: 116 (#enforced: 116)
#kLinearN: 1'353 (#enforced: 232) (#terms: 23'451)
#kNoOverlap: 8'796 (#intervals: 1'854'688, #optional: 1'853'656, #variable_sizes: 1'853'666, #fixed_intervals: 1'022)

Starting presolve at 0.12s
The solution hint is complete and is feasible. Its objective value is 0.

.

.

.
 #num_dual_strengthening=1

Presolve summary:
  - 2336 affine relations were detected.
  - rule 'TODO dual: add implied bound' was applied 15'555 times.
  - rule 'TODO dual: only one blocking constraint?' was applied 3'579 times.
  - rule 'TODO dual: only one blocking enforced constraint?' was applied 15'555 times.
  - rule 'affine: new relation' was applied 2'336 times.
  - rule 'at_most_one: removed literals' was applied 787 times.
  - rule 'at_most_one: size one' was applied 787 times.
  - rule 'at_most_one: transformed into max clique.' was applied 2 times.
  - rule 'bool_and: x => not x' was applied 62 times.
  - rule 'bool_and: x => x' was applied 62 times.
  - rule 'bool_or: always true' was applied 3'408 times.
  - rule 'bool_or: implications' was applied 854 times.
  - rule 'bool_or: only one literal' was applied 76 times.
  - rule 'bool_or: removed enforcement literal' was applied 992 times.
  - rule 'circuit: degree 2' was applied 6 times.
  - rule 'circuit: fixed singleton arcs.' was applied 1 time.
  - rule 'circuit: fully specified.' was applied 2 times.
  - rule 'circuit: removed false arcs.' was applied 19 times.
  - rule 'cumulative: max profile is always under the min capacity' was applied 1 time.
  - rule 'cumulative: removed intervals with a size of zero' was applied 8 times.
  - rule 'deductions: 30725 stored' was applied 1 time.
  - rule 'dual: add implication' was applied 1'656 times.
  - rule 'dual: enforced equivalence' was applied 62 times.
  - rule 'dual: fix variable' was applied 2'339 times.
  - rule 'dual: reduced domain' was applied 118 times.
  - rule 'duplicate: removed constraint' was applied 3'692 times.
  - rule 'enforcement: always false' was applied 1'530 times.
  - rule 'enforcement: false literal' was applied 21'660 times.
  - rule 'enforcement: true literal' was applied 83'469 times.
  - rule 'exactly_one: removed literals' was applied 1'115 times.
  - rule 'incompatible linear: add implication' was applied 1'506 times.
  - rule 'int_prod: boolean affine term' was applied 10'629 times.
  - rule 'intervals: change duplicate index across constraints' was applied 827 times.
  - rule 'intervals: removed unused interval' was applied 308 times.
  - rule 'lin_max: all exprs fixed during copy' was applied 8 times.
  - rule 'lin_max: converted to equality' was applied 2 times.
  - rule 'lin_max: removed exprs' was applied 1 time.
  - rule 'lin_max: target domain reduced' was applied 2 times.
  - rule 'linear + amo: fixed literal implied by enforcement' was applied 496 times.
  - rule 'linear1: always true' was applied 17 times.
  - rule 'linear1: x in domain' was applied 107 times.
  - rule 'linear: always true' was applied 14'404 times.
  - rule 'linear: divide by GCD' was applied 81 times.
  - rule 'linear: empty' was applied 1'690 times.
  - rule 'linear: enforcement literal in expression' was applied 3 times.
  - rule 'linear: fixed or dup variables' was applied 30'634 times.
  - rule 'linear: infeasible' was applied 14 times.
  - rule 'linear: positive equal one' was applied 1'111 times.
  - rule 'linear: reduced variable domains' was applied 9'024 times.
  - rule 'linear: remapped using affine relations' was applied 7'566 times.
  - rule 'linear: simplified rhs' was applied 1'442 times.
  - rule 'linear: singleton column' was applied 68 times.
  - rule 'linear: small Boolean expression' was applied 496 times.
  - rule 'new_bool: var with 2 values' was applied 81 times.
  - rule 'no_overlap: merged constraints' was applied 1 time.
  - rule 'no_overlap: no intervals' was applied 80 times.
  - rule 'no_overlap: only one interval' was applied 2'811 times.
  - rule 'no_overlap: removed absent intervals' was applied 4'817 times.
  - rule 'no_overlap: split into disjoint components' was applied 33 times.
  - rule 'presolve: 9179 unused variables removed.' was applied 1 time.
  - rule 'presolve: iteration' was applied 2 times.
  - rule 'variables with 2 values: create encoding literal' was applied 81 times.
  - rule 'variables with 2 values: new affine relation' was applied 81 times.
  - rule 'variables: detect half reified incompatible value' was applied 2 times.
  - rule 'variables: detect half reified value encoding' was applied 14'038 times.

Presolved optimization model '': (model_fingerprint: 0x279d6facf18dfa97)
#Variables: 46'314 (#bools: 1'181 in objective)
  - 10'878 Booleans in [0,1]
  - 184 different domains in [-1,12285] with a largest complexity of 16.
#kAtMostOne: 192 (#literals: 1'753)
#kBoolAnd: 1'544 (#enforced: 1'544) (#literals: 3'088)
#kCircuit: 9
#kCumulative: 9 (#intervals: 7'380, #optional: 7'380, #variable_sizes: 7'276)
#kExactlyOne: 1'098 (#literals: 8'935)
#kInterval: 8'972 (#enforced: 8'841) (#fixed: 32)
#kLinMax: 34 (#expressions: 168)
#kLinear1: 15'362 (#enforced: 15'362 #multi: 204)
#kLinear2: 76'304 (#enforced: 26'803 #multi: 1'428)
#kLinear3: 8'514 (#enforced: 8'415)
#kLinearN: 221 (#enforced: 34) (#terms: 8'851)
#kNoOverlap: 720 (#intervals: 142'450, #optional: 141'483, #variable_sizes: 140'351, #fixed_intervals: 859)
Stopped after presolve.
PresolvedNumVariables: 46314
PresolvedNumConstraints: 112979
PresolvedNumTerms: 305599
CpSolverResponse summary:
status: UNKNOWN
objective: 0
best_bound: 0
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 296.127
usertime: 296.127
deterministic_time: 0.801469
gap_integral: 0

status: UNKNOWN

If I run the same problem with e.g. max_time_in_seconds = 700 seconds, the solver finds a solution after around 300s.

2) Quite the opposite to the first problem. I give the solver a max_time_in_seconds_limit, but is runs much, much longer.
For example:

Starting CP-SAT solver v9.10.4067
Parameters: random_seed: 4 random_branches_ratio: 0.04 use_optimization_hints: true max_time_in_seconds: 1837 log_search_progress: true num_search_workers: 128 cp_model_probing_level: 4 max_presolve_iterations: 2 hint_conflict_limit: 75000 log_subsolver_statistics: false fix_variables_to_their_hinted_value: false probing_deterministic_time_limit: 0.4

Initial optimization model '': (model_fingerprint: 0xb8b644ba37214b85)
#Variables: 273'339 (#ints: 93 in objective)
  - 111'424 Booleans in [0,1]
  - 396 different domains in [-10000000,4105154649600] with a largest complexity of 15.
  - 4 constants in {1,2,3,12}
#kBoolOr: 10'426 (#enforced: 10'272) (#literals: 10'426)
#kCircuit: 31
#kCumulative: 32 (#intervals: 28393, #optional: 28393, #variable_sizes: 28393)
#kIntDiv: 190
#kIntProd: 60'102
#kInterval: 35'666 (#enforced: 32'381) (#fixed: 3284)
#kLinMax: 1'245 (#expressions: 2'672)
#kLinear1: 191'709 (#enforced: 191'567 #multi: 26'220)
#kLinear2: 328'982 (#enforced: 328'195 #multi: 34'214)
#kLinear3: 595 (#enforced: 270)
#kLinearN: 3'042 (#enforced: 617) (#terms: 167'260)
#kNoOverlap: 28'615 (#intervals: 6027757, #optional: 6024446, #variable_sizes: 6024473, #fixed_intervals: 3284)

Starting presolve at 0.61s
The solution hint is incomplete: 273335 out of 273339 variables hinted.

.

.

.
  
#kNoOverlap: 11'649 (#intervals: 3358286, #optional: 3356419, #variable_sizes: 3355901, #fixed_intervals: 1730)

Preloading model.
#Bound 299.16s best:inf   next:[1766397,407428889] initial_domain
#1     299.51s best:407428889 next:[1766397,407428888] complete_hint
#Model 301.20s var:228374/228375 constraints:616745/616745

Starting search at 301.53s with 128 workers.
17 full problem subsolvers: [core, default_lp, fixed, lb_tree_search, max_lp, no_lp, objective_lb_search, objective_lb_search_max_lp, objective_lb_search_no_lp, objective_shaving_search_max_lp, objective_shaving_search_no_lp, probing, probing_max_lp, pseudo_costs, quick_restart, quick_restart_no_lp, reduced_costs]
109 first solution subsolvers: [fj_long_default(5), fj_long_lin_default(5), fj_long_lin_perturb(4), fj_long_lin_random(4), fj_long_perturb(4), fj_long_random(5), fj_short_default(5), fj_short_lin_default(5), fj_short_lin_perturb(4), fj_short_lin_random(5), fj_short_perturb(4), fj_short_random(5), fs_random(14), fs_random_no_lp(13), fs_random_quick_restart(14), fs_random_quick_restart_no_lp(13)]
29 incomplete subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, rins/rens, rnd_cst_lns, rnd_var_lns, routing_full_path_lns, routing_path_lns, routing_random_lns, scheduling_intervals_lns, scheduling_precedences_lns, scheduling_resource_windows_lns, scheduling_time_window_lns, violation_ls(14)]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]
#Bound 308.27s best:407428889 next:[1766398,407428888] objective_shaving_search_no_lp (vars=228375 csts=634397)

.

.

.
#Model 1785.68s var:219946/228375 constraints:585134/616745
#Model 2147.98s var:219945/228375 constraints:585131/616745
#Model 2181.16s var:219942/228375 constraints:585131/616745
#Model 2184.57s var:219825/228375 constraints:584897/616745
#Bound 2429.43s best:406688544 next:[1801418,406688543] objective_shaving_search_max_lp (vars=220025 csts=586572)

.

.

.

CpSolverResponse summary:
status: FEASIBLE
objective: 406688544
best_bound: 1801418
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 3402.03
usertime: 3402.03
deterministic_time: 266.529
gap_integral: 5209.12
solution_fingerprint: 0x191e99df58170aba


status: FEASIBLE

[S. K.]

I am still having this problem. No one else?

Here is an example model where I get both problems:

Model Proto (zip-file containing the model proto text file in a GitHub repository)

At the moment I am using CP-SAT solver v9.12.4544. But the problem also occurs with version v9.10.

Parameters: random_seed: 2 random_branches_ratio: 0.04 use_optimization_hints: true max_time_in_seconds: 250 log_search_progress: true search_branching: AUTOMATIC_SEARCH cp_model_presolve: true num_search_workers: 12 cp_model_probing_level: 2 max_presolve_iterations: 1 hint_conflict_limit: 75000 log_subsolver_statistics: false fix_variables_to_their_hinted_value: false probing_deterministic_time_limit: 0.3

For example:

max_time_in_seconds = 400 s

One time the solver finds an optimal solution after 330s, but the wall and user time are 566.2728, so way more than 400 s (or in this case it should be even closer to 330 s, because the solver stops obviously after finding an optimal solution).

Another time the model "Stopped after presolve.", did not find a solution and the wall and user time are 320.09 s. So a good chunk of time before the 400 s.

max_time_in_seconds = 250 s

Again the solver "Stopped after presolve" and had a wall and user time of 188.78 s, so it stopped too early.

[Laurent Perron]

Fixed on main.

Thanks for the report.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/3ea91a17-9036-4033-8bf8-72a0534be59fn%40googlegroups.com.

[S. K.]

I upgraded to the newest version  v9.13.4784 after the release and still encounter the same problem (problem no. 1).

Here is the model I tested it with: model proto

Normally I am using the following solver parameters:

solver parameters: random_seed: 4
use_optimization_hints: true
max_time_in_seconds: 700
log_search_progress: true
num_search_workers: 12
max_presolve_iterations: 1
hint_conflict_limit: 75000
fix_variables_to_their_hinted_value: false
probing_deterministic_time_limit: 0.3

When I am using v9.10, the solver finds a solution after 81 seconds with no problems.

But when I am using v9.13 it stops after the presolve at 432 seconds (not using the full 700s from max_time_in_seconds) and I get a solver status UNKNOWN.

When I am using v9.13 and disabling the presolve, the solver finds a first (which is the hinted) solution after 0.92 seconds.

[S. K.]

I want to use v9.14, but it still has the same problem (problem 2 from the first post).

The time limit I give is not respected.

I am using a CP-SAT solver with the following parameters:

random_seed: 2
use_optimization_hints: true
max_time_in_seconds: 540
log_search_progress: true
cp_model_probing_level: 1 (or 0, it does not matter)
max_presolve_iterations: 1
merge_no_overlap_work_limit: 1e9 (or 1e8, it does not matter)

hint_conflict_limit: 75000
log_subsolver_statistics: false
fix_variables_to_their_hinted_value: false

num_workers: 120
probing_deterministic_time_limit: 0.3

Here is a model for testing purposes:

model: test model

With 2 models similar to the testing model, I encountered the problem that the solver does not stop AT ALL. It runs until I get a memory overload and the whole process is killed.

(Output of on example where the solver does not stop at all: output)

(Similar but slightly less complex models do not have this problem, or not as bad. They take maybe 10-30 seconds longer to stop if max_time_in_seconds = 300 s.)

In general I have the feeling that the v9.14 needs a lot more memory than v9.10, which I am currently using.

Laurent Perron schrieb am Mittwoch, 19. März 2025 um 21:24:55 UTC+1: