Primal Integral CP-SAT

[Priidik Vilumaa]

Hello,

I am trying to do small improvements on a CP-SAT Python model by rewriting some constraints and found that the primal_integral could give a quick estimate how good the model is.

1) Based on this image:  I can see that for a minimization problem smaller primal integral is better, as good solutions are found early. However, does this mean that for a maximization problem larger primal_integral is better?

2) Is the primal_integral only comparable for the same data?

3) Does the primal_integral change based on the best found solution/bound? I.e. if I don't solve the problem to optimality, then will the primal integral bounce around from run to run since the "baseline" is changing?

4) To sum it up: Is it a good metric to monitor and what's the correct way to do it?

Thanks,

Priidik

[Frederic Didier]

On Wednesday, November 10, 2021 at 9:10:09 AM UTC+1 vil...@gmail.com wrote:

Hello,

I am trying to do small improvements on a CP-SAT Python model by rewriting some constraints and found that the primal_integral could give a quick estimate how good the model is.

1) Based on this image:  I can see that for a minimization problem smaller primal integral is better, as good solutions are found early. However, does this mean that for a maximization problem larger primal_integral is better?

Are you talking about the primal-integral displayed by CP-SAT ? we use a non-standard formula...

First the gap is between the best bound and the best solution, so maximization or minimization will not change anything as the "gap" will always be positive and decreasing, reaching 0 at optimal.

I think the primal_ prefix is wrong, I will fix the name right away.

We don't use a relative gap, as adding a constant offset to the objective changes its definition.

Instead we use log(1+absolute_difference_between_two_objective) so we kind of track the order of magnitude of the gap.

And the graph changes each time we find a new solution or improve the best objective bound.

 

2) Is the primal_integral only comparable for the same data?

Probably yes, if you try to compare different model on the same problem, then a lower integral means a smallest gap faster.

 

3) Does the primal_integral change based on the best found solution/bound? I.e. if I don't solve the problem to optimality, then will the primal integral bounce around from run to run since the "baseline" is changing?

4) To sum it up: Is it a good metric to monitor and what's the correct way to do it?

We haven't used it extensively, so we cannot say :)

You can probably compute whatever formula you want instead of our custom one if you think it is a better fit for what you want to do.

 

Thanks,

Priidik

[Priidik Vilumaa]

Thank you for your answers. Yes, I was talking about the `primal_integral` as displayed in CP-SAT progress log/ ResponseStats.

My takeaway and current understanding is that when model1 will consistently give lower primal_integral than model2 for the same problem(s), then model1 is in fact better.