Improving Global Constraints Support by Local Search

Abstract. Most global constraints maintain a support for their filtering algorithm, namely a tuple consistent with both the constraint and current domains. However, this highly valuable information is rarely used outside of the constraint. In this paper we define the TV-Break Packing problem (TVBP) and we propose a generic hybridization scheme that we test on this real-world application. The principle of this Branch and Move approach is to use the support of the main global constraint of the problem as a guide for the branching strategy. The accuracy of this oracle is enhanced by local search improvements of this support tuple at each node of the search tree. 1