Bounding, filtering and diversification in CP-based local branching

Local branching is a general purpose heuristic method which searches lo- cally around the best known solution by employing tree search. It has been success- fully used in Mixed-Integer Programming where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. We pro- pose the integration of local branching in Constraint Programming (CP). This inte- gration is not simply a matter of implementation, but requires a number of significant extensions. The original contributions of this paper are: the definition of an efficient and incremental bound computation for the neighborhood, a cost-based filtering al- gorithm for the local branching constraint and a novel diversification strategy that can explore arbitrarily far regions of the search tree w.r.t. the already found solutions. We demonstrate the practical value of local branching in CP by providing an extensive experimental evaluation on the hard instances of the Asymmetric Traveling Salesman Problem with Time Windows.