Invariant Graph Propagation in Constraint-Based Local Search

In constraint-based local search, an assignment to the search variables is improved upon by an iterative procedure that replaces the current assignment with a similar assignment. The latter is selected by a heuristic that assesses the qualities of a subset of all similar assignments, where the quality of such assignments is determined via a process called invariant graph propagation. Since, typically, many similar assignments are considered in every iteration, invariant graph propagation must be as efficient as possible. Since invariant graph propagation is independent of the selection heuristic, any comparison between different invariant graph propagation styles under different selection heuristics can be misleading. In this paper, we describe and compare both theoretically and empirically the throughput of several invariant graph propagation styles, and give criteria when one style or another is to be used.