Using Group Theory to Construct and Characterize Metaheuristic Search Neighborhoods

Over the past four years, a Consortium composed of The University of Texas at Austin, the Air Force Institute of Technology and the US Air Force Air Mobility Command has been remarkably successful in developing the theoretical foundations of group theoretic tabu search (GTTS) and applying it to a set of complex military logistics problems. This paper briefly recounts some of those accomplishments and describes the underlying mathematical framework that supported them. The symmetric group on n letters, S

n

can be used to build and solve equations whose coefficients and variables are permutations, i.e., elements of S

n

. These equations efficiently describe search neighborhoods for combinatorial optimization problems (COPs) whose solutions can be modeled as partitions, orderings, or both (P|O problems). Following the introduction, the second section describes neighborhoods that preserve a cycle solution structure and recounts examples of how group theory has been used to provide new and useful insights into search neighborhoods. The third section describes neighborhoods for multiple cyclic solution structures. Section 4 considers a hybrid move neighborhood that borrows from Sections 2 and 3. The fifth section overviews some highly successful applications of the GTTS approach. The final section contains concluding remarks and offers suggestions for future work. The paper's goals are: (1) to illustrate that move neighborhoods can be cast into a group theoretic context and that new powerful neighborhoods can be easily “hand tailored” using group theory; and (2) to motivate others to consider how the unifying mathematical framework of group theory could be further exploited to gain powerful new understandings of direct search move neighborhoods.