Using OR-Tools with free search

[Aura Sofia]

Hello,

I have a question about using free search for the OR-Tools cp-sat solver. From what I understand, free search is always used in combination with a search strategy/annotation. Now, I ran cp-sat with and without the -f flag, but on the same model. The model does not contain search strategies. To my understanding, the -f flag should not yield a difference. However, using the -f flag results in a significant speed-up of the performance on all instances.

Why is that? What exactly does the -f flag do when used with cp-sat and "solve::satisfy;"?

From the Minizinc docs:

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.

 
What is meant by "prescribed strategy"?

Thank you for the help!

[Laurent Perron]

1) Free search does not need a search strategy.

2) without -f, and without a search strategy, CP-SAT defaults to a very basic heuristic.

3) -f launches an interleaved portfolio of workers which is quite good. This portfolio is implemented here: https://github.com/google/or-tools/blob/30e2067a971ca1e5bccdc0a6ef4917ad67d47363/ortools/flatzinc/cp_model_fz_solver.cc#L1686

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/c7187cc2-9dd6-42a0-869c-3c88ebcc0478n%40googlegroups.com.

[Erik Cervin Edin]

> What exactly does the -f flag do when used with cp-sat and "solve::satisfy;"?

In addition to Laurents explanation of what --free-search does, it
should be noted it only makes a difference if you are using -p 1 (the
default unless otherwise specified) which is single-threaded. If you
are using multiple workers, it's effectively the same as -f, except
the workers run on different threads.

In other words, free-search for the or-tools cp-sat is basically
emulating "multi-threaded solving" in a single-thread.

I did a short write-up here:
https://github.com/MiniZinc/libminizinc/issues/824#issuecomment-2393915080

Note that how it works for _solve satisfy_ is different from when optimizing:
https://github.com/google/or-tools/blob/30e2067a971ca1e5bccdc0a6ef4917ad67d47363/ortools/flatzinc/cp_model_fz_solver.cc#L1660C1-L1680C4

> What is meant by "prescribed strategy"?

Search annotations basically.

> To view this discussion visit https://groups.google.com/d/msgid/minizinc/CABcmEeaXtTLo%3DM_tG%3DXyRkUaX6N6eazkNSUavjCwomNA-f8USg%40mail.gmail.com.

[Erik Cervin Edin]

> Note that how it works for _solve satisfy_ is different from when optimizing:
https://github.com/google/or-tools/blob/30e2067a971ca1e5bccdc0a6ef4917ad67d47363/ortools/flatzinc/cp_model_fz_solver.cc#L1660C1-L1680C4

I should clarify, it only works differently if searching for all
solutions in solve satisfy.
Doesn't sound like that applies in this particular case.