Enhancements of branch and bound methods for the maximal constraint satisfaction problem
Richard J. Wallace · 1996
This paper will consider only the maximal constraint satisfaction problem (MAX-CSP), in which an optimal solution is one with a maximal number of satisfied constraints. There is reason to think that the results can be extended in a straightforward way to problems with weighted constraints (see [ SH81 ] ). Complete algorithms have been developed for MAX-CSPs that are based on branch and bound methods, using depth-first search ( [ FW92 ] ; see also [ SH81 ] ). Enhancements have also been developed that use information obtained from local consistency tests carried out before search. This information takes the form of inconsistency counts , i.e., tallies for each value