Abstract
In this paper we present a new branch and bound scheme for the Maximal Satisfaction Problem (MAX-CSP). Firstly, we formulate the problem as a Quadratic Assignment Problem (QAP). Then, using mathematical programming tools, a parametric lower bound of unsatisfied constraints is established. We show that the lower bound using directed are consistency counts is a particular case of the parametric lower bound. The flexibility of this bound allows us to determine a specific bound for each set of fixed parameters. In particular the bounds using weighted are consistency counts can be naturally described and integrated in a branch and bound scheme.
Our experiments show that the lower bound using are consistency counts has advantages over those using directed are consistency counts.