Randomize search parameter functionality

[Noah Rubin]

Hello, could someone explain how the  set_randomize_search parameter affects the solver?

There is very little documentation, and the parameter seems to significantly change the behavior of how the solver finds solutions (at least in my case). 

Thanks, 

Noah Rubin

[Laurent Perron]

which solver ? which version ?

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/477219f8-e2b5-4bb0-8de6-4db52da0944en%40googlegroups.com.

[Noah Rubin]

Using the CP-SAT solver in version 7.7

set_randomize_search(true) set in the SatParameters object, passed to the cp_model object.

[Curtis Bright]

The following comments concerning randomize_search are in sat_parameters.proto:

// Randomize fixed search.

// Search randomization will collect equivalent 'max valued' variables, and

// pick one randomly. For instance, if the variable strategy is CHOOSE_FIRST,

// all unassigned variables are equivalent. If the variable strategy is

// CHOOSE_LOWEST_MIN, and `lm` is the current lowest min of all unassigned

// variables, then the set of max valued variables will be all unassigned

// variables where

//    lm <= variable min <= lm + search_randomization_tolerance

As I understand it, if your search branching strategy is set to FIXED_SEARCH then search randomization causes the variable selection strategy to break ties randomly instead of using the order in which the variables were defined.

It's unclear what search randomization does when the branching strategy is kept to be the default (which uses the underlying SAT solver's heuristics to branch). Perhaps it simply randomizes the initial VSIDS activity values in the SAT solver?

Curtis