Accession Number:

ADA432696

Title:

A Group Theoretic Approach to Metaheuristic Local Search for Partitioning Problems

Descriptive Note:

Doctoral thesis

Corporate Author:

TEXAS UNIV AT AUSTIN

Personal Author(s):

Report Date:

2005-05-01

Pagination or Media Count:

123.0

Abstract:

Recent work has demonstrated the power of combining group theory with metaheuristic search methodologies to solve discrete optimization problems. Group theory provides tools to characterize the underlying structures in move neighborhoods, solution representations and solution landscapes. Exploiting these structures with group theoretic techniques produces highly effective and efficient search algorithms. Discrete optimization problems may be divided into three distinct groups partitioning, ordering and partitioning-and-ordering problems. Partitioning problems such as set covering, knapsack and min-cut network flow problems have no ordering context and require only that the solution variables be placed into mutually exclusive sets. Ordering problems such as single-agent traveling salesman, single-machine job shop scheduling and single-vehicle routing problems require that a permutation of the solution variables be stipulated. Partitioning-and-ordering problems such as multiple- agent traveling salesmen, multiple-machine job shop scheduling and multiple-vehicle routing problems require that the solution variables be partitioned and ordered within each partition.

Subject Categories:

  • Theoretical Mathematics
  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE