Using Google OR-Tools, CP-SAT, how do you make the optimization routine do a more thorough search?

Question

I'm using Google OR-Tools' CP-SAT to make a scheduling optimizer in C#. I used the examples, ShiftSchedulingSat and NursesSat as examples. My code is conceptually similar to ShiftSchedulingSat, in that I built a series of boolean requirements, as well as a list of terms with a bool * penalty in an array to be optimized, just as the obj in that example.

Similar to the example, I have several places where there is both a hard and soft requirement. I tried setting the hard requirement high, and the soft requirement low, to optimize on the value. The code returns within a second or two with a 'feasible' answer, but not optimal. I tried incrementally decrementing my hard requirement to manually find the lower bound. When it is + 1 or 2 of the lower bound I found, I get the 'optimal' answer; the soft requirement works! I don't understand in this model why it won't find the 'optimal' answer when the hard limits are increased. The code always returns in 1-2 seconds. Is there any way to make it look harder when searching for optimal?

I have tried running the above with many permutations on the StringParameters, including:

"num_search_workers:8, max_time_in_seconds:60";
"num_search_workers:8";  
"linearization_level:2, enumerate_all_solutions:true"

and pretty much every permutation of these options. I noticed that enumerate_all_solutions will cause the run time to increase profoundly, but always seems to stop around 29.9 seconds, even with the max_time_in_seconds set longer. I'm wondering if there's a bug that's causing it to stop searching at 30 seconds even with that option set. I have run the code without any optimization function, similar to the NursesSat example, and it will easily run for several minutes to enumerate 10 solutions, so I'm confused why adding optimization causes it to exit so quickly.

My thoughts are that there may be a bug causing it to timeout prematurely, there may be separate settings for the optimizing routine, which seems to be a separate linear optimization step, or that the linear optimization is getting caught in local minima and giving up easily.

Edit:

Here's relevent log output: Log output with the HardMax set to 4 Log output with the HardMax set to 5

I kept everything in my model same except modifying my hardmax of one constraint. The softmax was left the same to run the optimizer over. When the hardmax is set to 5, the optimizer achieves an output for the value in question of [ 2,4,4,4,4,4,4 ], but when I lower the hardmax to 4, the optimizer achieves an output of [ 2,3,3,3,3,3,3 ].

Looking at the logs, I can see that the linear optimizer is searching a lot more branch points when the hardmax is only 4, and it doesn't appear to generate any solutions at all when the hardmax is 5:

Search stats        Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag
     'default_lp':  2'372        450     6'584     4'746      42'203         36'841
          'no_lp':  2'372    207'791   637'173     6'640  25'221'620      4'908'163
         'max_lp':  2'372          0     5'180     4'744      21'870         30'859
           'core':  2'385    366'860   547'295     4'751  27'026'157      4'990'961
  'reduced_costs':  2'388          4     4'975     4'744      21'754         30'520
   'pseudo_costs':  2'385         10     5'576     4'745      23'418         33'435

LNS stats           Improv/Calls  Closed  Difficulty  TimeLimit
      'rins/rens':         41/41     46%        0.69       0.10
    'rnd_var_lns':           0/0      0%        0.50       0.10
    'rnd_cst_lns':           0/0      0%        0.50       0.10
  'graph_var_lns':           0/0      0%        0.50       0.10
  'graph_arc_lns':           0/0      0%        0.50       0.10
  'graph_cst_lns':           0/0      0%        0.50       0.10
  'graph_dec_lns':           0/0      0%        0.50       0.10

...

Solution repositories    Added  Queried  Ignored  Synchro
  'feasible solutions':      1        0        0        1  <---
        'lp solutions':     14        3        0        8  <---
                'pump':     40       38

vs

Search stats        Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag
     'default_lp':  2'715          0         0         0           0              2
          'no_lp':  2'715          0     3'972     3'972      21'243         28'774
         'max_lp':  2'715          0         0         0           0              1
           'core':  2'728          0     3'958     3'958      21'171         28'680
  'reduced_costs':  2'715          0     5'430     5'430      21'640         30'669
   'pseudo_costs':  2'715          0       576       576       2'669          3'497

...

Solution repositories    Added  Queried  Ignored  Synchro
  'feasible solutions':      1        0        0        1
        'lp solutions':      0        0        0        0
                'pump':      0        0

Gah!!! Nevermind... Just noticed this in the log.

Stop search after 1 solutions <--

I left the stop code from the nurse solution active and it was stopping the search prematurely. I've been grinding on this for days, but at least now I have a better knowledge of how CP-SAT works.

Using Google OR-Tools, CP-SAT, how do you make the optimization routine do a more thorough search?

Answers (1)

Related Questions