Efficient Interval Partitioning - Local Search Collaboration for Constraint Satisfaction

Abstract

In this article, a cooperative solution methodology that integrates interval partitioning (IP) algorithms with a local search, feasible sequential quadratic programming (FSQP), is presented as a technique to enhance the solving of continuous constraint satisfaction problems (continuous CSP). FSQP is invoked using a special search tree management system developed to increase search efficiency in finding feasible solutions. In this framework, we introduce a new symbolic method for selecting the subdivision directions that targets immediate reduction of the uncertainty related to constraint infeasibility in child boxes. This subdivision method is compared against two previously established partitioning rules (also parallelized in a similar manner) used in the interval literature and shown to improve the efficiency of IP. Further, the proposed tree management system is compared with tree management approaches that are classically used in IP. The whole method is compared with published results of established symbolic-numeric methods for solving CSP on a number of state-of-the-art benchmarks. (c) 2006 Elsevier Ltd. All rights reserved.