15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'03)
Implicit Random Constraint Satisfaction Problems
Sacramento, California, USA
November 03-November 05
ISBN: 0-7695-2038-3
Random CSPs (Constraint Satisfaction Problems) provide interesting benchmarks for experimental evaluation of algorithms. From a theoretical point of view, a lot of recent works have contributed to guarantee the existence of a so-called phase transition and, consequently, of hard and large problem instances. From a practical point of view, due to exponential space complexity, a vast majority of experiments based on random CSPs concerns binary problems. In this paper, we introduce a model of implicit random CSPs, i.e., of random CSPs where constraints are not given in extension but defined by a predicate. This new model involves an easy implementation, no space requirement and the possibility to perform experiments with large arity constraints.
Citation:
Christophe Lecoutre, Frédéric Boussemart, Fred Hemery, "Implicit Random Constraint Satisfaction Problems," ictai, pp.482, 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'03), 2003