The Constrainedness Knife-Edge

A general rule of thumbis to tackle the hardest part of a search problem first. Manyheuristics therefore try to branch on the most constrained variable. To test their effectiveness at this, we measure the constrainedness of a problem during search. Werun experiments in several different domains, using both random and non-random problems. In each case, we observe a constrainedness "knlfe-edge" in whichcritically constrained problems tend to remain critically constrained. Weshowthat this knife-edge is predicted by a theoretical lower-boundcalculation. Wealso observe a very simple scaling with problem size for various properties measuredduring search including the ratio of clauses to variables, and the averageclause size. Finally, weuse this picture of search to propose somebranching heuristics for propositionalsatisfiability. The Constrainedness Knife-Edge Toby Walsh APES Group Department of Computer Science University of Strathclyde Glasgow, Scotland tw©cs, strath, ac. uk deepens, over-constrained problemstend to become more constrained, but critically constrained problems from the region inbetween tend to remain critically constrained. We also observe a simple scaling with problem size for various properties measured during search including the ratio of clauses to variables. The existence of a constrainedness knife-edge helps to explain the hardness of problems from the phase transition. It also suggests some new branching heuristics for satisfiability. Similar microscopic studies that look closely inside search may be useful in other domains.

Authors

• Toby Walsh UNSW Sydney

Keywords

No keywords are indexed for this paper.