The Constrainedness Knife-Edge

Toby Walsh

A general rule of thumb is to tackle the hardest part of a search problem first. Many heuristics therefore try to branch ont he 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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.