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) : Kinney Jr, Gary W


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a432696.pdf


Report Date : May 2005


Pagination or Media Count : 123


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.


Descriptors :   *DISCRETE DISTRIBUTION , *HEURISTIC METHODS , *GROUPS(MATHEMATICS) , ALGORITHMS , METHODOLOGY , THEORY , THESES , VARIABLES , SOLUTIONS(GENERAL) , MULTIPLE OPERATION


Subject Categories : Theoretical Mathematics
      Statistics and Probability


Distribution Statement : APPROVED FOR PUBLIC RELEASE