Random Constraint Satisfaction: Flaws and Structure
Research Report 98.23, School of Computer Studies, University of Leeds,
October 1998.
Ian P Gent, Ewan MacIntyre, Patrick Prosser, Barbara M Smith and Toby
Walsh
Abstract
A recent theoretical result by Achlioptas et al. shows that conventional
models of random problems are trivially insoluble in the limit. This
insolubility is due to the presence of `flawed variables', variables whose
values are all `flawed' (or unsupported). 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
flawed variables can be expected to occur. We also study an alternative
model of random problems proposed by Achlioptas et al. to tackle such
flaws. We show that flawed values still occur in this model at problem sizes
similar to those used in practice. To eliminate flawed values and variables, we
introduce a `flawless' generator by putting a limited amount of structure
into the conflict matrix. We also show how to introduce structure into
the constraint graph. We can thereby generate ensembles of problems that are
not trivially insoluble due to the presence of flawed variables, as well as
problems that contain structures in their constraint graphs which are rare
in purely random problems.
Back to "Barbara Smith
- Publications on Constraint Programming"