How efficient is a global constraint in practice?: A fair experimental framework

Propagation is at the very core of t can provide signi: it can provide significant performance boosts as long as the search space reduction is not outweighed by the cost for running the propagators. A lot of research effort in the CP community is directed toward improving this trade-off. While experimental evaluation is here of the greatest importance, there exists no systematic and flexible methodology to measure the exact benefits provided by a given (new) filtering procedure. This work proposes such a framework by relying on replaying search trees to obtain more realistic assessments. Reducing propagation overhead is done chiefly by 1) devising more efficient algorithms or by 2) using on-line control policies to limit the propagator activations, i.e., mechanisms to reduce the number of propagator calls. In both cases, obtaining improvements is a long and demanding process with uncertain outcome. We propose a method to assess the potential gain of both approaches before actually starting the endeavor, providing the community with a tool to best direct the research efforts. In order to visualize benefits of actual global constraints and the potential of their improvement, we suggest the use of performance profiles. Our approach is showcased for well-known global constraints: alldifferent, cumulative, binpacking and unary (with transition times).