This project is sponsored by Air Force Office of Scientific Research, Air Force Materiel Command, United States Air Force, under grant number FA9550-11-1-0088.

Project Description

Our project focuses on exploiting information about evaluations of solutions in the search space to make search more efficient and more effective. In particular, there are a number of NP-hard optimization problems where the search space can be characterized as an elementary landscape. For these search spaces the evaluation function is an eigenfunction of the Laplacian matrix that describes the neighborhood structure of the search space. Problems such as the Traveling Salesman Problem (TSP), Graph Coloring, the Frequency Assignment Problem, as well as Min-Cut and Max-Cut Graph Partitioning and select satisfiability problems all have elementary landscapes. We have also proven that all k-bounded pseudo-Boolean optimization problems (including MAX-kSAT and NK-landscapes) can be expressed as a superposition of k elementary landscapes.

For all elementary landscapes one can efficiently compute neighborhood average evaluations, as well as other statistics, without actually evaluating any neighbors. Moreover, the computation can be applied to regions of the search space as well as single points. We are exploiting these computations to develop new divide-and-conquer algorithms. For example, for the TSP, we have developed a new crossover operator that improves the current state of the art algorithm, Lin-Kernighan-Helsgaun 2, in difficult clustered instances. In both NK-Landscapes and MAX-SAT, we exploit Walsh Computations to perform next ascent search in constant time. Our methods for elementary landscape computations and search algorithms that exploit the properties will be extended to Vehicle Routing Problems, Graph Coloring and select scheduling problems.

We are a subgroup of the Artificial Intelligence Group in the Computer Science Department of Colorado State University.