Counting Solutions of CSPs: A Structural Approach
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 260-264.
Abstract
Determining the number of solutions of a CSP has several applications in AI, in statistical physics, and in guiding backtrack search heuristics. It is a #Pcomplete problem for which some exact and approximate algorithms have been designed. Successful CSP models often use high-arity, global constraints to capture the structure of a problem. This paper exploits such structure and derives polytime evaluations of the number of solutions of individual constraints. These may be combined to approximate the total number of solutions or used to guide search heuristics. We give algorithms for several of the main families of constraints and discuss the possible uses of such solution counts.
@inproceedings{ijcai2005p56,
title = {Counting Solutions of CSPs: A Structural Approach},
author = {Pesant, Gilles},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {260--264},
year = {2005},
url = {https://ijcai.org/proceedings/2005/56},
}
TY - CPAPER TI - Counting Solutions of CSPs: A Structural Approach AU - Pesant, Gilles T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 260 EP - 264 UR - https://ijcai.org/proceedings/2005/56 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
