The Constrainedness Knife-Edge

Abstract

A general rule of thumb is to tackle the hardest part of a search problem first. Many heuristics therefore try to branch on the most constrained variable. To test their effectiveness at this, we measure the constrainedness of a problem during search. We run experiments in several different domains, using both random and non-random problems. In each case, we observe a constrainedness "knife-edge" in which critically constrained problems tend to remain critically constrained. We show that this knife-edge is predicted by a theoretical lower-bound calculation. We also observe a very simple scaling with problem size for various properties measured during search including the ratio of clauses to variables, and the average clause size. Finally, we use this picture of search to propose some branching heuristics for propositional satisfiability. Introduction Empirical studies of search procedures usually focus on statistics like the run-time or the total number of nodes visited. It can also be...