Accession Number:

ADA622665

Title:

Exploiting Elementary Landscapes for TSP, Vehicle Routing and Scheduling

Descriptive Note:

Final rept. 1 Jun 2011-31 May 2015

Corporate Author:

COLORADO STATE UNIV FORT COLLINS

Personal Author(s):

Report Date:

2015-09-03

Pagination or Media Count:

25.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE