cp-sat option -f search strategy

[Samrat Kadge]

Minizinc User manual 3.5.13 states:

A search annotation (see Search) can be useful, however allowing OR-Tools to mix the prescribed strategy with its own (option -f) usually is best, analogously to Chuffed.

***********************************

Which search strategy does the option -f correspond to?

Which subsolver follows this strategy?

In sat_parameters, the following options are available.

 AUTOMATIC_SEARCH = 0;
 FIXED_SEARCH = 1;
 PORTFOLIO_SEARCH = 2;
 LP_SEARCH = 3;
 PSEUDO_COST_SEARCH = 4;
 PORTFOLIO_WITH_QUICK_RESTART_SEARCH = 5;
 HINT_SEARCH = 6;
 PARTIAL_FIXED_SEARCH = 7;
 RANDOMIZED_SEARCH = 8;

[Laurent Perron]

It is a portfolio. You should read the code, or the log at that start of the search. 

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 "MiniZinc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/minizinc/1ccdee92-2afe-4e58-976f-413aa4dcac6an%40googlegroups.com.

[Samrat Kadge]

Thanks Laurent

I think I have some understanding, after reading the code 
e,g GetNamedParameters in cp_model_search.cc

Log:

without option:      search_branching: AUTOMATIC_SEARCH

with option:            search_branching: FIXED_SEARCH

This affects the base_params from which a subsolver is derived.

So any subsolver which uses the default value for search_branching in base_params, will be affected.

[Laurent Perron]

I meant the code in OR-tools/flatzinc/cp_model_fz_solver.cc

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

To view this discussion visit https://groups.google.com/d/msgid/minizinc/e796059d-c808-4297-9da0-a26086cecbaen%40googlegroups.com.

[Erik]

As Laurent alluded to, the best way to truly understand it is to go looking at the source-code

I wrote a short summary on what --free-search (-f) means when using CP-SAT solver as a FZN backend here:
https://github.com/MiniZinc/libminizinc/issues/824#issuecomment-2393915080

In a nutshell, it's useful when you can't run 8 threads or more (-p 8) because then OR-Tools CP-SAT can only run in a single thread (which is terrible for OR-Tools CP-SAT performance.) With --free-search, OR-Tools CP-SAT will interleave the different workers in a single-thread. In essence, this gives you the some of the benefit of the portfolio of different workers without having to use multiple threads.

That said. You should use as many threads as possible when using OR-Tools as the solver.