Computing at Glasgow University
Paper ID: 8580

Random Constraint Satisfaction: Theory Meets Practice
MacIntyre,E. Prosser,P. Smith,B.M.

Publication Type: Conference Proceedings
Appeared in: Principles and Practice of Constraint Programming - CP98: 4th International Conference, CP98, Pisa, Italy, October 1998. Proceedings
Page Numbers : 325-339
Publisher: LNCS, Springer
Year: 1998
ISBN/ISSN: 1611-3349

We study the experimental consequences of a recent theoretical result by Achlioptas et al. that shows that conventional models of random problems are trivially insoluble in the limit. We survey the literature to identify experimental studies that lie within the scope of this result. We then estimate theoretically and measure experimentally the size at which problems start to become trivially insoluble. Our results demonstrate that most (but not all) of these experimental studies are luckily unaffected by this result. We also study an alternative model of random problems that does not suffer from this asymptotic weakness. We show that, at a typical problem size used in experimental studies, this model looks similar to conventional models. Finally, we generalize this model so that we can independently adjust the constraint tightness and density.

Keywords: random constraint satisfaction problems

PDF Bibtex entry Endnote XML