Dynamic domain splitting for numeric CSPs

Abstract

. In this paper, a new search technique over numeric csps is presented: dynamic domain splitting. The usual search technique over numeric csps is a dichotomic search interleaved with a consistency filtering, which is called domain splitting. This paper proposes to replace chronological backtracking at the core of domain splitting by a non destructive backtracking technique. 1 Introduction Many industrial and engineering problems can be seen as constraint satisfaction problems (csps). A csp is defined by a set of variables each with an associated domain of possible values and a set of constraints on the variables. This paper deals with csps where the constraints are numeric relations and where the domains are either finite integer domains or continuous domains (numeric csps). Numeric csps can be used to express a large number of problems, in particular physical models involving imprecise data or partially defined parameters. In general, numeric csps cannot be tackled with computer al...