An Adaptive Search for the NSCSPs

Recently we proposed, in [ACZ03], a framework to address both soft and continuous constraints. We call it Numerical Semiring-based Constraint Satisfaction Problem (NSCSP). This approach extends Semiring based CSP (SCSP) as Numerical CSP (NCSP) does for CSP. Solving NSCSPs is often a task of finding the ”best ” solution(s). It can be seen as an optimisation problem. NSCSPs have a huge search space. With such a space, non-complete methods provide very good results in a short time. Since a few years, the CSP community has a growing interest in these methods to solve the CSPs and the soft CSPs as it has been shown in [BFLL03]. This paper presents the actual state of our work around the algorithm of Adaptive Search proposed by Codognet and Diaz in [CD01]. We want to use this algorithm to solve the optimisation task of the NSCSP framework. After presenting the general algorithm, we will focus our presentation on some interesting neighbourhoods for our goal: finding a ”best/good ” solution for a NSCSP