Keynote speakers:

Constrainedness of Search
   Prof. Toby Walsh

    (NICTA and University of New South Wales)

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 "knife-edge", critically constrained between easy, under-constrained instances and obviously over-constrained instances. Heuristics that try to get off this knife-edge 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:



FOGA XII is sponsored by ACM SIGEVO, You can join SIGEVO here.
FOGA XII is supported by The University of Adelaide

FOGA 2011   FOGA 2009     FOGA 2007     FOGA 2005      FOGA 7

* First seven FOGA (1990 -- 2002) published by Morgan Kaufmann