ToOLS

ToOLS: A library for partial and hybrid search methods. We present a library called ToOLS for the design of customized tree search algorithms in a Constraint Programming (CP) framework. We separate the description of search algorithms into three parts: a refinement-based search scheme which defines a complete search tree, a set of conditions for visiting nodes which specifies a parameterized partial exploration, and a temporal strategy for combining several partial explorations. This library allows to express most of the partial, i.e. non systematic backtracking, search methods and also, a specific class of hybrid local/global search methods called Large Neighborhood Search, which is very naturally suited to CP technology. Variants of those methods are easy to implement with the ToOLS primitives. We demonstrate the expressiveness and efficiency of the library by solving a mission management problem which is a mix between a travel-ing salesman problem with time windows and a knapsack problem. Several partial and hybrid search methods are compared. The best results we get are close to the ones obtained by a dedicated algorithm and drastically outperform CP approaches based on classical depth-first search methods