Enhancements of Branch and Bound Methods for the Maximal Constraint Satisfaction Problem
Abstract
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
Cite
Text
Wallace. "Enhancements of Branch and Bound Methods for the Maximal Constraint Satisfaction Problem." AAAI Conference on Artificial Intelligence, 1996.Markdown
[Wallace. "Enhancements of Branch and Bound Methods for the Maximal Constraint Satisfaction Problem." AAAI Conference on Artificial Intelligence, 1996.](https://mlanthology.org/aaai/1996/wallace1996aaai-enhancements/)BibTeX
@inproceedings{wallace1996aaai-enhancements,
title = {{Enhancements of Branch and Bound Methods for the Maximal Constraint Satisfaction Problem}},
author = {Wallace, Richard J.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1996},
pages = {188-195},
url = {https://mlanthology.org/aaai/1996/wallace1996aaai-enhancements/}
}