Exploiting Elementary Landscapes for TSP, Vehicle Routing and Scheduling
Final rept. 1 Jun 2011-31 May 2015
COLORADO STATE UNIV FORT COLLINS
Pagination or Media Count:
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 and Graph Coloring are elementary. Problems such as MAX-kSAT are a superposition of k elementary landscapes. This research has exploited statistical and mathematical properties of elementary landscapes to develop new gradient methods for combinatorial optimization problems, particular for TSP and MAXSAT and other k-bounded pseudo-Boolean optimization problems.
- Operations Research