Monitor search in CP-SAT solver

[Giacomo Da Col]

Dear all,

I just started using the new CP-SAT solver. In the original CP solver there was the possibility to monitor the search using a SearchMonitor. Is there something similar for the new solver? In particular, I would need to see how the variables’ domains evolve during the search.

Thanks a lot!

Giacomo

[Laurent Perron]

It is not available. Search is very different in a sat solver. 

--
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/008201d4ff3a%24eacf57b0%24c06e0710%24%40gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Giacomo Da Col]

Thank you very much for the quick reply!

So there is no way to see what’s going on during the search? I explain you my problem:

I have a really basic job-shob scheduling problem, I need to measure the performance (in terms of makespan achieved within a timeout) using two models:

-model 1: No use of interval variables, so every operation is modelled with start and end variables, and a constraint addEqualityWithOffset to impose start+duration=end

-model 2: Every operation is modelled with start and end variables and interval variables, which already ensure start+duration=end without additional constraints.

 

In both cases I do not use any global constraint, such as NoOverlap, Cumulative, alldiff (this is a strict requirement).

Thus, the non overlapping propriety is ensured by the following constraints:

model.addLessOrEqual(end_i,start_j).onlyEnforceIf(dummy);

model.addLessOrEqual(end_j,start_i).onlyEnforceIf(dummy.not());

for each couple of operations i j and boolean variables dummy.

Given this setup, I have that model1 outperforms model2 by a wide margin, and I have to understand why. My guess is that the introduction of Interval variables without using NoOverlap or Cumulative messes up the propagation in model 2, but I have to prove it.

Do you have any suggestions on why this is happening, or can you suggest me a way to find that out?

Many Thanks

Giacomo

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAPyyUTuaCQ%3DGwofSkLpE44zjuZ4gXHUYu2xqaXjaeuYvnagUvA%40mail.gmail.com.

[Laurent Perron]

Quick ideas for benchmarking:

Generate lots of models that run in a reasonable time (< 1 min) to optimality.

Run all of them, store running time, number of conflicts.

Change the model, rerun and compare.

There is too much luck in search to conclude from 1 example.

In your example, the linear relaxation will pick up the equality constraint, but not the interval equivalent. It may explain the difference in performance.

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/00c401d4ff5a%24a29f37b0%24e7dda710%24%40gmail.com.

[Giacomo Da Col]

Dear Laurent,

I run some tests on:

- B1 = a benchmark of 10  10x10 (10 jobs on 10 machines) instances

- B2 = a benchmark of 10  10x100 (10 jobs on 100 machines) instances.

Concerning the number of conflicts, there is not a huge difference between model1 and model2 in both benchmarks, however, there is a big difference in the number of branches and the time needed to find the optimal solution:

In particular:

-          On B1, model2 generates about 10 times the branches of model1, and arrives to the optimal solution in about 5 times the time needed to model1 (20 seconds instead of 4).

 

-          On B2, model2 generates about 30 times the branches of model1, and arrives to the optimal solution in about 40 times the time needed to model1 (400 seconds instead of 10).

 

I could send you a file with more precise information, but that was the summary.

 

Can you suggest an explanation for this behavior?

Also, could you explain a little bit more in detail the linear relaxation bit?

Thanks a lot for your help

Giacomo

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEebgx%2Bi1a%3D71oOCG%3DNv%2BmC3L%3DdnDj0rWe4jZgWrbOam9uQ%40mail.gmail.com.

[Laurent Perron]

As I said, the CP-SAT solver embeds a simplex for more propagation.

This simplex is fed the equations from model1, but not the intervals from model2.

And this simplex can be used to guide the search. I guess it will be useful.

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/00c901d5003d%24ca3b59f0%245eb20dd0%24%40gmail.com.

[Giacomo Da Col]

I see, thanks a lot for your help!

Is there a citable source where I can find the description on this resolution method? Is it similar to the temporal linearization done by CP Optimizer (ILOG)?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeZFw%3DwSN36SWh5t%3D56_zqP606Ly2Q2bkQ-Ng2LDnCL1CA%40mail.gmail.com.

[Laurent Perron]

This is an old technique that was popular 20 years ago under the name hybrid solving. Nothing spectacular :-)

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

De : Giacomo Da Col <jack...@gmail.com>
Date : dim. 12 mai 2019 à 19:36
À : <or-tools...@googlegroups.com>

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/002701d508e9%243e4bb9d0%24bae32d70%24%40gmail.com.