Filtering Decomposable Global Cost Functions
Abstract
As (Lee et al., 2012) have shown, weighted constraint satisfaction problems can benefit from the introduction of global cost functions, leading to a new Cost Function Programming paradigm. In this paper, we explore the possibility of decomposing global cost functions in such a way that enforcing soft local consistencies on the decomposition offers guarantees on the level of consistency enforced on the original global cost function. We show that directional arc consistency and virtual arc consistency offer such guarantees. We conclude by experiments on decomposable cost functions showing that decompositions may be very useful to easily integrate efficient global cost functions in solvers.
Cite
Text
Allouche et al. "Filtering Decomposable Global Cost Functions." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8124Markdown
[Allouche et al. "Filtering Decomposable Global Cost Functions." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/allouche2012aaai-filtering/) doi:10.1609/AAAI.V26I1.8124BibTeX
@inproceedings{allouche2012aaai-filtering,
title = {{Filtering Decomposable Global Cost Functions}},
author = {Allouche, David and Bessiere, Christian and Boizumault, Patrice and de Givry, Simon and Gutierrez, Patricia and Loudni, Samir and Métivier, Jean-Philippe and Schiex, Thomas},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {407-413},
doi = {10.1609/AAAI.V26I1.8124},
url = {https://mlanthology.org/aaai/2012/allouche2012aaai-filtering/}
}