Deterministic execution time for CP Sat

[Marc]

I’ve read that with NumSearchWorkers = 1 and an optimization function, the search should be deterministic. I have a case where I get the same, optimal, solution every time. But the execution time varies by an order of magnitude. Sometimes arriving at that answer in 2 to 3 seconds and sometimes takes 30 seconds or more. Is that normal? I would have expected a deterministic algorithm to have a somewhat stable execution time.

I’m attaching the output from logSearchProgress and the exported ProtoBufs of one fast run (“seconds-2.8…”) and one slow run (“seconds-34…”). I’m wondering if there are any hints to explain the discrepancy.

My setup:
OR-Tools 9.4.1874
Mac OS 12.4
Java
EnumerateAllSolutions true
SatParameters.SearchBranching.FIXED_SEARCH
DecisionStrategy:
  VariableSelectionStrategy/CHOOSE_FIRST
  DomainReductionStrategy/SELECT_MIN_VALUE

Marc

[Frederic Didier]

Your two proto models are not the same (see output of diff ~/Downloads/seconds-2.8-model.pb.txt ~/Downloads/seconds-34-model.pb.txt), likely the order of variable and/or constraint changed.

This will lead to different behavior of the solver.

If you want to be deterministic, you need the code that constructs the model to be deterministic too. 

Likely you iterate over hash-map or other construct that might change from one run to the next.

--
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/c23ec297-5326-44a5-8bce-7e1c7727e460n%40googlegroups.com.

[Marc]

Awesome, fd.  This makes sense.  I'll experiment over the next few days and report back here.

[Marc]

So just to close the loop here, fd's response here was spot on.  I had several hash-maps with information about my variables and looping through them to create the variables in the model happened was non-deterministic.  After replacing all those with "ordered maps", I now get deterministic behavior and consistent run times that are two orders of magnitude improvement over my previous worst case.

Thanks for the suggestion.

Marc