how measure performance of cp-sat for comparison with heuristic methods ?

[gregy4]

Hello,
I found that cp-sat performs well for multi-skill resource constrained scheduling problem. Unfortunatelly, most papers on this topic focus on heuristic methods and it is hard to compare it. For cp-sat seems natural calculation time but it is hardware dependent, heuristic methods often use evolution algorithms and use for example number of found solutions or measure explored state space.

Can be for example some statistics like number of branches or propagations from summary useful in the comparison with heuristic methods?

Thanks,
Jan

[sschnug]

No. The statistics you mention are imho completely useless for this comparison.

As optimality-proofs are the exception for hard problems like that and because heuristic methods lack optimality-proofs anyway, the (imho most) natural approach (which also is quite compatible with end-users / practical applications) would be looking at the best-incumbent over time.

See: Combinatorial Optimization at Work 2024: Berthold MILP Heuristics for an example.

Remarks:

• The linked resource focuses on integer-programming which also provides dual-bounds as CP-SAT does
  • You might want to ignore those or introduce a constant bound
• The linked resource considers some internal statistics as useful
  • But this only works as the scope is comparing the same solver(-approach) with different sub-heuristics

Extract from Link:

Or some old graphs of mine (please ignore the numbers!):