Title: Modeling Combinatorial Search Spaces

Speaker: Andrew Sutton, Colorado State University

Date/Time: Thursday, July 1, 2010, 1:00 pm       

Location: CSRI Building/Room 90 (Sandia NM)

Brief Abstract: Many combinatorial optimization problems can be solved or quickly approximated by heuristic search algorithms that perform local perturbations to complete candidate solutions (e.g., local search and some variants of evolutionary algorithms). The dynamics of such algorithms depend on the structure of the search space.  A good model of the search space should capture this structure and allow us to 1) analyze some of its basic properties, 2) predict the dynamics of algorithms, and 3) design algorithms in a more principled manner.

In this talk I will present an approach to modeling combinatorial search spaces that takes advantage of the fact that many common objective functions can be decomposed into subfunctions that have some nice properties. I will show how the model can be used to efficiently compute statistics of the distribution of objective function values over local regions of the search space. These statistics can be used to predict the number of improving moves in a volume of the space. Finally, I will present an application of the model in the design of a heuristic that guides local search through plateaus:

CSRI POC: Jean-Paul Watson, 505-845-8887