Abstract
In this paper, we propose a new way for representing and solving constraintsatisfaction problems (CSPs). We first show that a CSP can be modelized by a single pseudo-Boolean function. Then some theoretical results establishing the links between a CSP and its associated pseudo-Boolean function are described. We propose a Branch and Bound method exploiting this representation for solving CSPs. This method follows the same scheme developed by the Forward-Checking procedure. The main difference between the Branch and bound method and the Forward-Checking method lies in the computation performed at every node of the search tree. The Branch and Bound method uses the constraints in an active way to infer a knowledge about the problem. Then a solution or failure may be detected quickly.