Understanding the [hint] in the CP-SAT log

[Nara Torres Moreira]

Hello,

I'm experienced with OR using commercial solvers but I'm new using CP, and I'm struggling to understand some behaviours of CP-SAT (v9.3.10497).

I have a multi-objective problem and I'm solving it in phases, where each phase focuses on a specific objective. Each phase solves the same model, except for the objective function and (in case it is not the 1st phase) additional constraints added so that the previous achieved objectives are satisfied, and an initial feasible solution.

- What is the best way to understand the log in more details? Is there any documentation that explains its main bits?

- The first thing I find strange is that sometimes the initial solution is not used, and there is no reference to the hint in the logs (e.g. nothing saying the hint is not feasible). I know that with different workers the hint might not be tested immediately, but I would still expect to see something that shows me that it was considered at some [early] point of the search (for a certain case the solver ran for 900s with 4 workers).

- Sometimes the hint is applied, but many seconds have already passed.

- Also, currently my initial solution is not complete. My hint contains the values for all "important variables", but some auxiliary variables are not being informed. Could that be an issue?

- Another thing I don't understand is that sometimes I see multiple references to [hint] in the log (example below). What does that mean? Is this the same "user solution" concept? Is it possible to have that printed if I did not provide a hint (otherwise I might have a bug in my code)?

#25      4.53s best:882   next:[84,881]   rnd_var_lns_default(d=0.79 s=498 t=0.10 p=0.75) [hint]
#26      4.69s best:873   next:[84,872]   rnd_cst_lns_default(d=0.75 s=499 t=0.10 p=0.75) [hint]
#27      5.03s best:864   next:[84,863]   rnd_var_lns_default(d=0.70 s=503 t=0.10 p=0.60) [hint]
#28      5.14s best:856   next:[84,855]   rnd_cst_lns_default(d=0.65 s=504 t=0.10 p=0.60)
#29      5.94s best:840   next:[84,839]   rnd_var_lns_default(d=0.78 s=508 t=0.10 p=0.67)
#30      6.19s best:834   next:[84,833]   graph_cst_lns_default(d=0.78 s=511 t=0.10 p=0.67)
#31      7.18s best:826   next:[84,825]   rnd_cst_lns_default(d=0.65 s=524 t=0.10 p=0.56)
#32     10.79s best:818   next:[84,817]   rnd_var_lns_default(d=0.82 s=543 t=0.10 p=0.62)
#33     13.18s best:816   next:[84,815]   default_lp fixed_bools:0/18745
#34     13.41s best:808   next:[84,807]   rnd_var_lns_default(d=0.77 s=558 t=0.10 p=0.56)
#35     13.97s best:802   next:[84,801]   rnd_var_lns_default(d=0.71 s=563 t=0.10 p=0.53)
#36     16.58s best:794   next:[84,793]   rnd_var_lns_default(d=0.77 s=578 t=0.10 p=0.55)
#37     23.89s best:756   next:[84,755]   rins_lns_default_lp(d=0.00 s=617 t=0.10 p=0.00)
#38     24.19s best:748   next:[84,747]   rnd_cst_lns_default(d=0.70 s=619 t=0.10 p=0.54) [hint]
#39     25.07s best:746   next:[84,745]   rnd_cst_lns_default(d=0.64 s=624 t=0.10 p=0.52)


Thank you! Any help is very appreciated.

Nara

[Laurent Perron]

There should be a message near the start of the log about the hint

During search, in a LNS worker, we hint the previous solution. If it helps finding an improving solution, it displays the [hint] tag.

--
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/d3d83c57-05e9-4ae4-8c03-62b22cbdf570n%40googlegroups.com.

[Nara Torres Moreira]

Hi Laurent, thank you for the quick answer.

>> There should be a message near the start of the log about the hint

The only message referring to "hint" that I see is in the beginning of the search, when it is applied. For example:

Starting Search at 0.44s with 4 workers.
2 full subsolvers: [default_lp, no_lp]
Interleaved subsolvers: [feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, rins_lns_default, rens_lns_default]
#Bound   0.49s best:inf   next:[1327,12439] no_lp initial_propagation
#1       0.49s best:5243  next:[1327,5242] no_lp [hint] fixed_bools:3/2952
#2       0.52s best:5143  next:[1327,5142] no_lp fixed_bools:3/2952

Was there supposed to be any other message before that, so that I know that a hint was indeed informed to the solver, and to differentiate to the case when the hint was simply not applied before the time limit?

>> During search, in a LNS worker, we hint the previous solution. If it helps finding an improving solution, it displays the [hint] tag

Ahh brilliant, thank you, that makes sense now.