1、,AAAI00Austin, Texas,Generating Satisfiable Problem Instances Dimitris Achlioptas Microsoft Carla P. Gomes Cornell University Henry Kautz University of Washington Bart Selman Cornell University,Introduction,An important factor in the development of search methods is the availability of good benchmar
2、ks.Sources for benchmarks: Real world instances hard to find too specific Random generators easier to control (size/hardness),Random Generators of Instances,Understanding threshhold phenomena lets us tune the hardness of problem instances: At low ratios of constraints - most satisfiable, easy to fin
3、d assignments; At high ratios of constraints - most unsatisfiable easy to show inconsistency; At the phase transition between these two regions roughly half of the instances are satisfiable and we find a concentration of computationally hard instances.,Limitation of Random Generators,PROBLEM: evalua
4、ting incomplete local search algorithms Filtering out Unsat Instances - use a complete method and throw away unsat instances. Problem: want to test on instances too large for any complete method! “Forced” Formulas Problem: the resulting instances are easy have many satisfying assignments,Outline,I G
5、eneration of only satisfiable instancesII New phase transition in the space of satisfiable instancesIII Connection between hardness of satisfiable instances and new phase transitionIV Conclusions,Generation of only satisfiable instances,Given an N X N matrix, and given N colors, color the matrix in
6、such a way that:-all cells are colored;- each color occurs exactly once in each row;- each color occurs exactly once in each column;,Quasigroup or Latin Square,Quasigroup or Latin Squares,Quasigroup Completion Problem (QCP),Given a partial assignment of colors (10 colors in this case), can the parti
7、al quasigroup (latin square) be completed so we obtain a full quasigroup?Example:,32% preassignment,QCP: A Framework for Studying Search,NP-Complete. Random instances have structure not found in random k-SAT Closer to “real world” problems! Can control hardness via % preassignment BUT problem of cre
8、ating large, guaranteed satisfiable instances remains,(Anderson 85, Colbourn 83, 84, Denes & Keedwell 94, Fujita et al. 93, Gent et al. 99, Gomes & Selman 97, Gomes et al. 98, Shaw et al. 98, Walsh 99 ),Quasigroup with Holes (QWH),Given a full quasigroup, “punch” holes into it,Difficulty: how to gen
9、erate the full quasigroup, uniformly.,Question: does this give challenging instances?,Markov Chain Monte Carlo (MCMM),We use a Markov chain Monte Carlo method (MCMM) whose stationary (egodic) distribution is uniform over the space of NxN quasigroups (Jacobson and Matthews 96). Start with arbitrary L
10、atin Square Random walk on a sequence of Squares obtained via local modifications,Generation of Quasigroup with Holes (QWH),Use MCMM to generate solved Latin Square Punch holes - i.e., uncolor a fraction of the entries The resulting instances are guaranteed satisfiable QWH is NP-Hard Is there % hole
11、s where instances truly hard on average?,Easy-Hard-Easy Pattern in Backtracking Search,% holes,Computational Cost,QWH peaks near 32% (QCP peaks near 42%),Easy-Hard-Easy Pattern in Local Search,% holes,Computational Cost,First solid statistics for overconstrainted area!,Phase Transition in QWH?,QWH -
12、 all instances are satisfiable - does it still make sense to talk about a phase transition? The standard phase transition corresponds to the area with 50% SAT/UNSAT instances Here all instances SAT Does some other property of the wffs show an abrupt change around “hard” region?,Backbone,Number sols
13、= 4,Backbone is the shared structure of all solutions to a given instance (not counting preassigned cells),Phase Transition in the Backbone,We have observed a transition in the size of backbone Many holes backbone close to 0% Fewer holes backbone close to 100% Abrupt transition coincides with hardes
14、t instances!,New Phase Transition in Backbone,% Backbone,% holes,Computational cost,% of Backbone,Why correlation between backbone and problem hardness?,Intuitions: Local Search Near 0% Backbone = many solutions = easy to find by chance Near 100% Backbone = solutions tightly clustered = all the cons
15、traints “vote” in same direction 50% Backbone = solutions in different clusters = different clauses push search toward different clusters,(Current work verify intuitions!),Why correlation between backbone and problem hardness?,Intuitions: Backtracking searchBad assignments to backbone variables near
16、 root of search tree cause the algorithm to deteriorateFor the algorithm to have a significant chance of making bad choices, a non-negligible fraction of variables must appear in the backbone,Reparameterization of Backbone,% of Backbone,Backbone for different orders (30 - 57),Reparameterization Comp
17、utational Cost,Computational Cost different orders (30, 33, 36),% of Backbone,Local Search (normalized),Local Search (normalized & reparameterized),Summary,QWH is a problem generator for satisfiable instances (only): Easy to tune hardness Exhibits more realistic structure Well-suited for the study o
18、f incomplete search methods (as well as complete) Confirmation of easy-hard-easy pattern in computational cost for local search New kind of phase transition in backbone Reparameterization GOAL new insights into practical complexity of problem solving,QWH generator, demos, available soon ( one month): www.cs.cornell.edu/gomes www.cs.washington.edu/home/kautz SATLIB CSPLIB,Parameterization,% of Backbone,Backbone for different orders (30 - 57),
