Exploiting Elementary Landscapes for TSP, Vehicle Routing and Scheduling

Abstract : 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.