Counting-Based Search for Constraint Optimization Problems
Abstract
Branching heuristics based on counting solutions in constraints have been quite good at guiding search to solve constraint satisfaction problems. But do they perform as well for constraint optimization problems? We propose an adaptation of counting-based search for optimization, show how to modify solution density computation for some of the most frequently-occurring constraints, and empirically evaluate its performance on several benchmark problems.
Cite
Text
Pesant. "Counting-Based Search for Constraint Optimization Problems." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10433Markdown
[Pesant. "Counting-Based Search for Constraint Optimization Problems." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/pesant2016aaai-counting/) doi:10.1609/AAAI.V30I1.10433BibTeX
@inproceedings{pesant2016aaai-counting,
title = {{Counting-Based Search for Constraint Optimization Problems}},
author = {Pesant, Gilles},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {3441-3448},
doi = {10.1609/AAAI.V30I1.10433},
url = {https://mlanthology.org/aaai/2016/pesant2016aaai-counting/}
}