Towards the Complexity of Differentiation Through Lazy Updates in Local Search Engines

Differentiation is an efficient technique to quickly explore neighbourhoods in local search optimization. It allows evaluating neighbours without updating the model, eliminating in this way the need for backtracking technical speed). Also, some invariants have better complexity for differentiation than for update, because they do not need to modify their internal data structures. However in the context of generic CBLS tools, differentiation is hard to implement efficiently.

We present an approach that often manages to reduce the complexity of invariant updates to the one of differentiation. In move-and-backtrack setting, successive updates on an invariant often annihilate each other. We therefore propose the idea of lazy update of the internal data structures of the invariants. Moves that have no impact on the output of the invariant are not performed on the time-consuming internal data structures. Instead, they are put on a backlog list. Opposite moves in the backlog annihilate each other and are never performed. Backlogs only needs to be performed when the output is impacted by an update.

This approach tries to approach the complexity of differentiation, although it will never reach the same technical speed as differentiation. However, we claim that lazy internal updates are more generic than differentiation, as they can work on any problem including routing and scheduling, and that it will be effective on a wider set of moves than differentiation.

Voir en ligne : Site web ORBEL