Constrainedness of Search
Prof. Toby Walsh
(NICTA and University of New South Wales)
http://www.cse.unsw.edu.au/~tw/
Will a problem be satisfiable or unsatisfiable? Will it be hard or easy? How can we develop heuristics for new problem domains? A discuss a general method which helps to answer such questions that is applicable to a wide range of combinatorial problems.
My starting point is a definition of the constrainedness of a combinatorial problem.
Measuring the constrainedness of problems during search also provides insight into why some problems are harder to solve than others. I show that hard problems are often on a constrainedness "knifeedge", critically constrained between easy, underconstrained instances and obviously overconstrained instances. Heuristics that try to get off this knifeedge as quickly as possible by, for example, minimizing the constrainedness are often therefore very effective.
Joint work with Patrick Prosser, Ian Gent and others. =
For more info, please visit: http://www.cse.unsw.edu.au/~tw/foga13.ppt
