CP-SAT Custom combination of subsolvers

[Mark]

I have a scheduling problem in python where the log reveals that most solutions are found with the "no_lp" sub_solver.  This is good and progresses quickly, but it starts very far away from the optimal solution.  A more traditional (CHOOSE_LOWEST_MIN, SELECT_MIN_VALUE) fixed search jumps immediately to a near-optimal solution, but then doesn't improve to optimality as quickly.

Q1:  Given 8 virtual cores, is it possible in python to specify to use "no_lp" on 4, and fixed_search on 4?  If so, how?

Q2:  It's been a while since I used the portfolio of sub-solvers and I see things have changed since then.  When viewing the log with 8 search workers it lists more than 8 sub-solvers [ default_lp, fixed, pseudo_costs, no_lp, max_lp, feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, scheduling_time_window_lns_default, scheduling_random_lns_default, rins_lns_default, rens_lns_default ].  search_branching is set to FIXED_SEARCH, so I don't have portfolio-based search enabled nor interleaved-search yet all of these sub-solvers are definitely running periodically since they'll return the occasional intermediate solution.  Are they cycled based upon conflicts/restarts, and which parameter controls this?

[Laurent Perron]

1) No. no_lp and fixed_search as mostly deterministic. So duplicating them will not help.

2) default_lp, fixed, pseudo_costs, no_lp, max_lp, and core are complete solvers. Fixed will only be included if a search strategy is defined. Core will only be included if the objective is a sum.

The rest of the workers will cycle across the remaining lns + feasibility pump.

It you have more that 8 workers, we add quick_restart.

more that 10, we add quick_restart_no_lp.

more that 12, we add probing, and we recently introduced lb_tree_search.

See https://github.com/google/or-tools/blob/dd85ab7a037091450284d7ae15853efc6d5807a4/ortools/sat/cp_model_search.cc#L499

For the record, we tune for 8 and 16 workers. Mostly for 16 workers lately.

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/f2c3c999-b35d-4dc9-ab26-82ee495fda54n%40googlegroups.com.

[Mark]

I'm now solving a problem with a sum objective for which the core-based solvers should be ideally suited.  

Indeed the "core" sub-solver seems to perform much better than the others.  

I am now hoping to be able to try the max_hs variant as well for comparison.

Am I successfully swapping the thread running the regular core algorithm for a single core running the max_hs algorithm when I add the following parameters?:

solver.parameters.num_search_workers = 8

solver.optimize_with_core = True
solver.optimize_with_max_hs = True

The end result is that I still see solutions produced by no_lp, lns, core, etc, but there's no indication whether this has successfully changed from regular core to max_hs.

Also, ORTools is able to access Gurobi on my installation; is there any way to tell the max_hs algorithm to use Gurobi as its MIP solver rather than, presumably the default, cbc?

[Laurent Perron]

I am not even sure the max_hs parameter is relevant, it if it just ignored. 

And no, it was hard coded to use scip or CBC. 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/b6bf4326-4157-4f0d-bf27-cd30fe49eb5dn%40googlegroups.com.