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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 03, 2015
Accession Number
ADA622665

Entities

People

  • Adele E. Howe
  • L. D. Whitley

Organizations

  • Colorado State University

Tags

Communities of Interest

  • Cyber
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Air Force Research Laboratories
  • Algorithms
  • Computations
  • Computer Science
  • Cybersecurity
  • Electronic Mail
  • Engineering
  • Evolutionary Algorithms
  • Genetic Algorithms
  • Mathematics
  • Operations Research
  • Optimization
  • Scheduling (Production)
  • Statistics
  • Test And Evaluation
  • Theoretical Computer Science

Readers

  • Linear Algebra
  • Mathematical Modeling and Probability Theory.
  • Operations Research

Technology Areas

  • Space