CODEWITHSUNDEEP
pythonor-toolscp-sat
Andrew
Andrew

Reputation: 549

Seeding the CP-SAT solver

In googles OR-tools library, the "Original" CP-Solver (discussed here: https://developers.google.com/optimization/cp/original_cp_solver) can be reseeded using .ReSeed(). However, the newer version, CP-SAT cannot.

My assumption is that CP-SAT will exhaustively try every option in your problem, taking the maximum or minimum (depending on your optimisation goal) from the ones that are feasible. Because it tries them all no seeding is required, therefore the option isn't available to you.

Is this understanding correct? If I am, why does the original solver have a seeding? If I am not correct, is the lack of .ReSeed() in the new CpSolver an oversight?

Upvotes: 2

Views: 2653

Answers (1)

sascha
sascha

Reputation: 33532

No, your reasoning is not quite correct.

Yes, the CP-SAT solver will try every option and will find a solution in finite time or prove infeasibility (under some mild conditions: i won't try to go into details except for mentioning the most simple limitation -> memory; less simple: random-restart progression). This nature of a solver is usually termed complete and (sound) (the latter referring to the fact that there will never be wrongly classified output like infeasibility when it is feasible). But the original CP-Solver is also complete and sound.

Seeding should never be used as tuning-parameter (and use-cases are pretty limited). The seed is used as PRNG-init (there is randomness in the solver, but it's deterministic) and it might make sense to use this fact in competitions (to render out luck or non-helpful tuning).

As mentioned in the comment by @Stradivari there is a seed in the protobuf definition. Those can be set too, if you want.

It might look like this:

from ortools.sat.python import cp_model

solver = cp_model.CpSolver()
solver.parameters.random_seed = 10

This shows the python interface, but the protobuf files are compiled for all those supported languages and therefore those setters should be available in all APIs (imho).

If i remember correctly, the manually set parameters will be shown to you at solve-start time (or there is some way to obtain this information for some additional check).

Upvotes: 6

Related Questions