CP-SAT poor performance

[Oliver Beattie]

I am modelling what appears to me, as someone unfamiliar with the inner workings of the CP-SAT solver, to be the kind of problem that the solver is designed to handle, but the performance degrades hugely under specific conditions. I'm wondering what I am doing wrong, or could be doing differently, to get better performance.

In short, I have tasks with compressible lengths which I want to be scheduled sequentially, maximising the number of time that's scheduled overall. This has good performance when the constraints allow all events to be scheduled, but becomes far poorer when some events (modelled as optional intervals) need to be left unscheduled.

I've attached a minimal model proto that for me takes a long time to solve despite only trying to optimise only 4 intervals. The version attached takes >2 mins to solve on 8 cores, but if I reduce the number of intervals to 3 it only takes ≈200ms. This performance difference seems really drastic.

I am investigating tuning the search strategies at the moment, but I've seen the general advice is to improve the model instead. Nothing I've tried has helped much, but I'm also not sure what I should be trying. Can I model this differently to improve things?

Really appreciate any pointers you can give! Thanks for bearing with someone new to this area.

– Oliver

[Frederic Didier]

Maybe try to reduce your time precision ? you have pretty high bounds:

#Variables: 20 (#ints:4 in objective)
  - 4 Booleans in [0,1]
  - 4 in [0][864000,950400]
  - 4 in [0,1814400]
  - 8 in [1640995200,1642809600]

The solver seems to find the optimal solution quickly but has trouble proving it is optimal.

And using such high numbers might cause precision issues with the linear programming solver so we cannot fully exploit its deductions.

--
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/f7d84e51-262c-433c-871b-ece49c5a7f19n%40googlegroups.com.

[Oliver Beattie]

Thanks so much for your quick reply. Really appreciate it.

I've taken your suggestions of reducing the precision and also narrowed the bounds by using a custom epoch. This has definitely helped somewhat, but I am still seeing poorer performance than I'd hope for. In the attached example there are more intervals (now 15), but they are using much smaller bounds:

      #Variables: 75 (#ints:15 in objective)
        - 30 in [0][600,660]
        - 15 in [0][600,1920]
        - 15 in [0,1]
        - 15 in [0,1320]

Despite this, I see similar behaviour where the solver finds the optimal solution very quickly but then takes quite a long time to prove that it is optimal:

     Interleaved subsolvers: [feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, scheduling_time_window_lns_default, scheduling_random_lns_default, rins_lns_default, rens_lns_default]
      #Bound   0.01s best:-inf  next:[-0,19798] bool_core num_cores:1 [core:3 mw:1 d:0] assumptions:13 depth:2 fixed_bools:0/81
      #Bound   0.01s best:-inf  next:[-0,19796] bool_core num_cores:2 [core:1 mw:1 d:2] assumptions:13 depth:2 fixed_bools:0/86
      #Bound   0.01s best:-inf  next:[-0,19794] bool_core num_cores:3 [core:1 mw:1 d:2] assumptions:13 depth:2 fixed_bools:1/91
      #1       0.01s best:3840  next:[3842,19794] default_lp fixed_bools:0/72
      #Bound   0.01s best:3840  next:[3842,19792] bool_core num_cores:4 [core:1 mw:1 d:2] assumptions:13 depth:2 fixed_bools:2/96

      […]

      #Bound   42.01s best:3840  next:[3842,5248] default_lp

      #Done    42.12s default_lp

Is there any more that you could recommend I do to optimise this?

Cheers,

Oliver