Randomness in CP-SAT search

[Thomas B]

Hello,

I have a CP model that solves to optimality. Then I rerun the model with a new constraint that the former objective function can only be == the optimum. This is how I create multiple solutions with the optimal objective value.

I noticed that I get different solutions for a CP model if I run the same model on the same PC. 

If I set the number of workers = 1 the results are always the same. But I get fewer solutions than in default mode. Is there another way to create deterministic behavior to get more solutions?

Also, I get a different solution if I run the same model on another machine. Is there a way to force the solver to search for the same solutions on different machines?

Thank you very much!

Sincerely

Thomas

[Laurent Perron]

I need some clarifications:

  - you create a model. Solve to optimality. add a constraint obj == optimal value, then rerun ?

  - do you remove the objective, and use enumerate_all_solutions:true ?

Default parallel search is not deterministic. Single thread search should be deterministic.

Is it exactly the same model ? meaning the same underlying protobuf? Or could the order of constraints or variables depend on the architecture ? It can happen if you use hash_maps.

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/2bcfe0bb-c652-4c9d-9377-6a32de4c03bcn%40googlegroups.com.

[Thomas B]

- yes, I solve to optimality, add a constraint obj == optimal value, then rerun

- I remove the objective

-  enumerate_all_solutions is = true now

Single thread search is deterministic for the same machine. So my problem with one machine is solved, tanks!

BUT

I only want to find 10 solutions, but they should always be the same no matter which machine.

The model is exactly the same, the ortools version also, but the python version is different (3.10 and 3.7), could that be an issue?

[Laurent Perron]

The best way to make sure is to save the model in proto format on both arch, and compare the output.

saving: model.ExportToFile('model.pb.txt')

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/0b113d06-f66c-40ed-a06d-0ef34e918bd7n%40googlegroups.com.

[Thomas B]

The models are identical on both machines.

[Thomas B]

I checked it with model.ExportToFile('model.pb.txt')

[Frederic Didier]

It is probably a bug on our side then, can you send us the model.pb.txt so we can have a look?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/14a87bd6-b140-46a6-9df5-42395b7335c6n%40googlegroups.com.

[Thomas B]

Yes, I attached both outputs.

[Frederic Didier]

Actually, after a bit of testing, I am not sure there is something we can do.

If you compile with different compilers on the different platforms, there is no guarantee the floating point computations will be done in the same order...

You can try to run your model with the parameters "linearization_level:0", since this disables the LP, we have almost no floating-point computation involved, and you should hopefully get the same solution.

It is not 100% guaranteed as we still use floating points for variable activities and other things.

Otherwise if your platforms are compatible, maybe you can use the same binary on both which should give the same result.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/15050e81-a200-48d9-bf66-db9e632bf942n%40googlegroups.com.

[Thomas B]

Thank you very much for that tip.

Setting the parameter "linearization_level:0" helps.

A problem that occurred now is that some instances take very long to solve. With the parameter "linearization_level:1" they get solved really fast.

Could you tell me what the parameter does? So I may figure out how to solve this issue.

Greetings 

Thomas

[Laurent Perron]

It uses a linear relaxation and a simplex to help. 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/0e1d0401-ec65-45ab-b362-b17566a493d9n%40googlegroups.com.