Investigation of methods for solving new classes of quadratic assignment problems (QAPs)

In this dissertation, I consider two new classes of Quadratic Assignment Problems: The Quadratic 3-dimensional Assignment Problem (Q3AP) and the Generalized Quadratic Assignment Problem (GQAP). Chapters 3 and 4 of this dissertation report on the development of algorithms for solving the Quadratic 3-dimensional Assignment Problem. The motivation for the Q3AP is the implementation of a hybrid ARQ (Automatic Repeat reQuest) scheme for enriching diversity among multiple packet transmissions by optimizing the mapping of transmission symbols to data. My preliminary results illustrate just how difficult it is to solve the Q3AP. I investigate four approximate solution methods (three developed by me) that provide optimum or near optimum solutions for large and difficult QAP instances and apply them to Q3AP instances of size 8, 9, 12, 15 and 16. Hence, the results of my experiments make it possible to get good solutions to signal mapping problems of size 8 and 16. I also present herein improvements I have made to an exact solution method based upon a reformulation linearization technique that is one of the best available for solving the QAP. This current exact algorithm is useful for Q3AP instances of size 13 or smaller. The goal of future work is to extend the range of these techniques to signal mapping problems as large as size 32 and 64. Chapter 5 of this dissertation reports on a new exact solution method and an approximation solution method for solving the Generalized Quadratic Assignment Problem. GQAP describes a broad class of integer programming problems, wherein M inter-related entities are assigned to N destinations, constrained by the destinations\u27 ability to accommodate them. This new exact algorithm is partially based on a reformulation linearization technique that I enhanced by adding a subgradient optimization step. Experimental results show that the computational complexity of this algorithm is comparable to other known exact solution methods, and that its runtime is as good or better than those methods for problems as large as M=30 and N=20. I also present an approximate solution method for GQAP. This approximate solution method uses new evaluations of neighboring solutions for various strategies for exploring the neighborhood. These strategies result in a method that, compared to other known approximate techniques, provides the optimal solution on small size instances (less than M=12 and N=9) and good quality solutions in competitive computational times on large size instances (as large as M=50 and N=20)