Performance of cumulative and reservoir constraints in cp_model

[Samuel Brown]

Hello

I am using ORTools in Python to solve a scheduling problem for N members of staff. Unlike most of the examples I've seen, I am trying not to specify the shift times in advance. Instead, each shift is modelled as an interval variable, and I am trying to optimise the shift times over a week. The total number of hours to be allocated is fixed (at 36*N hours) and other standard constraints apply, e.g. on the allowable shift lengths, break lengths, transition from night to day shifts etc. The final constraints are about staff coverage, e.g. "there must be at least 2 members of staff on duty between 6am and 10am every weekday".

Having researched previous questions on this type of problem, I have managed to implement models using both a reservoir constraint (with the water level as "staff on duty" minus "required coverage") and a cumulative constraint (on the complement of the shift intervals). In both cases I have used a single constraint for the entire week. The trouble is, both of these approaches lead to the model taking far too long to solve: even for small values (N=3 or 4) it is often running for 20-30 minutes without finding a solution or terminating. Without these constraints, the model runs happily in well under a second.

I am fairly new to constraint programming so would value any intuition on whether this problem is inherently too difficult, or any tips for how to formulate these constraints so that they perform quickly. The alternative approach -- to specify the possible shift times in advance -- is much more performant but doesn't give the flexibility that I am looking for.

My setup: ORTools 9.9.3963, Python 3.12 on WSL, tried up to 16 workers.

Thank you very much!

Sam

[Laurent Perron]

You can have a look here:

https://github.com/google/or-tools/blob/main/ortools/sat/docs/scheduling.md#cumulative-constraint-with-min-and-max-capacity-profile

Now, 

1) make sure the model has a solution. Inject a feasible solution to check that

2) if you can build a solution by hand, you can pass it as a hint

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 on the web visit https://groups.google.com/d/msgid/or-tools-discuss/a7a96eda-69e3-4c2f-8ec4-22d96df8f366n%40googlegroups.com.

[Samuel Brown]

Hello Laurent, and thank you very much for the reply!

That example you linked is very helpful - it's what led me to create a cumulative constraint to model the "minimum" coverage level. Injecting a feasible solution as a hint is a good tip, although I'm unsure if that would help me in the long run (I need to create lots of solutions quickly with different parameters, rather than optimise an existing or known solution).

I think I have set up the model correctly following your example. I have implemented some of my constraints but not all, but am currently just looking for any feasible solution (no objective function yet). The solver log output is below - I would be very interested in any insight this provides!

Thanks again

Sam

Starting CP-SAT solver v9.9.3963
Parameters: log_search_progress: true num_search_workers: 8

Initial satisfaction model '': (model_fingerprint: 0x73cdacc3ff4dc229)
#Variables: 145
  - 56 Booleans in [0,1]
  - 28 in [0,24]
  - 60 in [0,36]
  - 1 constants in {1}
#kBoolOr: 28 (#literals: 28)
#kCumulative: 1 (#intervals: 60, #variable_sizes: 32, #fixed_intervals: 28)
#kInterval: 60 (#fixed: 28)
#kLinear1: 84 (#enforced: 84)
#kLinear2: 196 (#enforced: 168 #multi: 84)
#kLinear3: 32
#kLinearN: 1 (#terms: 56)
#kNoOverlap: 5 (#intervals: 60, #variable_sizes: 32, #fixed_intervals: 28)

Starting presolve at 0.00s
  3.55e-04s  0.00e+00d  [DetectDominanceRelations]
  3.30e-03s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
  2.61e-05s  0.00e+00d  [ExtractEncodingFromLinear]
[SAT presolve] num removable Booleans: 0 / 56
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:28 literals:56 vars:56 one_side_vars:56 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.00027415s] clauses:28 literals:56 vars:56 one_side_vars:56 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.00033485s] clauses:28 literals:56 vars:56 one_side_vars:56 simple_definition:0 singleton_clauses:0
  5.50e-03s  3.55e-04d  [Probe] #probed=400 #new_bounds=28 #new_binary_clauses=184
  7.15e-05s  0.00e+00d  [MaxClique]
  7.59e-05s  0.00e+00d  [DetectDominanceRelations]
  8.81e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
  1.10e-04s  0.00e+00d  [ProcessAtMostOneAndLinear]
  3.90e-04s  0.00e+00d  [DetectDuplicateConstraints] #duplicates=28
  2.86e-04s  2.34e-06d  [DetectDominatedLinearConstraints] #relevant_constraints=61 #num_inclusions=28
  2.77e-05s  0.00e+00d  [DetectDifferentVariables]
  7.76e-05s  1.68e-07d  [ProcessSetPPC] #relevant_constraints=28
  3.63e-05s  6.00e-08d  [FindAlmostIdenticalLinearConstraints] #num_tested_pairs=4 #found=4
  2.58e-05s  1.15e-05d  [FindBigAtMostOneAndLinearOverlap]
  3.93e-05s  3.30e-05d  [FindBigVerticalLinearOverlap]
  5.72e-06s  2.80e-07d  [FindBigHorizontalLinearOverlap] #linears=1
  3.33e-06s  0.00e+00d  [MergeClauses]
  6.28e-05s  0.00e+00d  [DetectDominanceRelations]
  5.53e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
  5.51e-05s  0.00e+00d  [DetectDominanceRelations]
  4.49e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
[SAT presolve] num removable Booleans: 0 / 56
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:28 literals:56 vars:56 one_side_vars:56 simple_definition:0 singleton_clauses:0
[SAT presolve] [2.81e-05s] clauses:28 literals:56 vars:56 one_side_vars:56 simple_definition:0 singleton_clauses:0
[SAT presolve] [3.3128e-05s] clauses:28 literals:56 vars:56 one_side_vars:56 simple_definition:0 singleton_clauses:0
  2.34e-03s  3.24e-04d  [Probe] #probed=392 #new_binary_clauses=196
  4.63e-05s  0.00e+00d  [MaxClique]
  4.83e-05s  0.00e+00d  [DetectDominanceRelations]
  3.87e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
  4.33e-05s  0.00e+00d  [ProcessAtMostOneAndLinear]
  1.33e-04s  0.00e+00d  [DetectDuplicateConstraints]
  1.35e-04s  2.30e-06d  [DetectDominatedLinearConstraints] #relevant_constraints=57 #num_inclusions=28
  1.63e-05s  0.00e+00d  [DetectDifferentVariables]
  1.28e-05s  1.68e-07d  [ProcessSetPPC] #relevant_constraints=28
  8.18e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints]
  1.78e-05s  1.15e-05d  [FindBigAtMostOneAndLinearOverlap]
  2.59e-05s  3.30e-05d  [FindBigVerticalLinearOverlap]
  3.66e-06s  2.80e-07d  [FindBigHorizontalLinearOverlap] #linears=1
  2.71e-06s  0.00e+00d  [MergeClauses]
  4.68e-05s  0.00e+00d  [DetectDominanceRelations]
  3.57e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
  4.25e-05s  0.00e+00d  [DetectDominanceRelations]
  3.28e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
[SAT presolve] num removable Booleans: 0 / 56
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:28 literals:56 vars:56 one_side_vars:56 simple_definition:0 singleton_clauses:0
[SAT presolve] [2.571e-05s] clauses:28 literals:56 vars:56 one_side_vars:56 simple_definition:0 singleton_clauses:0
[SAT presolve] [2.974e-05s] clauses:28 literals:56 vars:56 one_side_vars:56 simple_definition:0 singleton_clauses:0
  1.80e-03s  3.24e-04d  [Probe] #probed=392 #new_binary_clauses=196
  3.23e-05s  0.00e+00d  [MaxClique]
  3.94e-05s  0.00e+00d  [DetectDominanceRelations]
  3.15e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
  3.73e-05s  0.00e+00d  [ProcessAtMostOneAndLinear]
  3.77e-04s  0.00e+00d  [DetectDuplicateConstraints]
  4.87e-04s  2.30e-06d  [DetectDominatedLinearConstraints] #relevant_constraints=57 #num_inclusions=28
  3.34e-05s  0.00e+00d  [DetectDifferentVariables]
  2.69e-05s  1.68e-07d  [ProcessSetPPC] #relevant_constraints=28
  1.22e-05s  0.00e+00d  [FindAlmostIdenticalLinearConstraints]
  3.08e-05s  1.15e-05d  [FindBigAtMostOneAndLinearOverlap]
  4.74e-05s  3.30e-05d  [FindBigVerticalLinearOverlap]
  7.47e-06s  2.80e-07d  [FindBigHorizontalLinearOverlap] #linears=1
  4.82e-06s  0.00e+00d  [MergeClauses]
  2.56e-04s  0.00e+00d  [DetectDominanceRelations]
  1.17e-03s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1

Presolve summary:
  - 4 affine relations were detected.
  - rule 'TODO dual: only one blocking enforced constraint?' was applied 252 times.
  - rule 'TODO linear inclusion: superset is equality' was applied 84 times.
  - rule 'affine: new relation' was applied 4 times.
  - rule 'bool_or: always true' was applied 28 times.
  - rule 'deductions: 112 stored' was applied 1 time.
  - rule 'duplicate: merged rhs of linear constraint' was applied 28 times.
  - rule 'duplicate: removed constraint' was applied 28 times.
  - rule 'incompatible linear: add implication' was applied 84 times.
  - rule 'linear: advanced affine relation from 2 constraints.' was applied 4 times.
  - rule 'linear: remapped using affine relations' was applied 7 times.
  - rule 'linear: simplified rhs' was applied 252 times.
  - rule 'no_overlap: split into disjoint components' was applied 1 time.
  - rule 'presolve: 1 unused variables removed.' was applied 1 time.
  - rule 'presolve: iteration' was applied 3 times.
  - rule 'probing: simplified enforcement list.' was applied 28 times.
  - rule 'variables: detect half reified value encoding' was applied 56 times.

Presolved satisfaction model '': (model_fingerprint: 0xee20219b34400244)
#Variables: 140
  - 56 Booleans in [0,1]
  - 28 in [0,24]
  - 28 in [0,36]
  - 28 in [6,36]
#kBoolAnd: 28 (#enforced: 28) (#literals: 56)
#kCumulative: 1 (#intervals: 60, #variable_sizes: 32, #fixed_intervals: 28)
#kInterval: 60 (#fixed: 28)
#kLinear1: 56 (#enforced: 56)
#kLinear2: 168 (#enforced: 140 #multi: 84)
#kLinear3: 28
#kLinearN: 1 (#terms: 56)
#kNoOverlap: 4 (#intervals: 32, #variable_sizes: 32)

Preloading model.
#Model   0.03s var:140/140 constraints:346/346

Starting search at 0.03s with 8 workers.
6 full problem subsolvers: [default_lp, fixed, max_lp, no_lp, quick_restart, quick_restart_no_lp]
1 first solution subsolver: [fj_short_default]
2 incomplete subsolvers: [feasibility_pump, rins/rens]
2 helper subsolvers: [neighborhood_helper, synchronization_agent]

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/rfKSnfBfQ6c/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeanEBxVa%3DCX1T8HrebXQROZskthQa6P8WV%3DaOL6Yde8pg%40mail.gmail.com.