Algorithms and theoretical topics on selected combinatorial optimization problems

We study the Quadratic Assignment Problem (QAP), Three Dimensional Assignment Problem (3AP) and Quadratic Three Dimensional Assignment Problem (Q3AP), which combines aspects of both QAP and 3AP. The three problems are known to be NP-hard. We propose new algorithms for obtaining near optimal solutions of QAP and 3AP and present computational results. Our algorithms obtain improved solutions in some benchmark instances of QAP and 3AP. We also discuss theoretical results on 3AP and Q3AP such as polynomially solvable special cases and approximation algorithms. A special case of 3AP is the constant 3AP where every feasible solution has the same cost. Necessary and sufficient conditions are presented for an instance of 3AP to have a constant solution and the result is extended to Multidimensional Assignment Problems (MAP).