On the quadratic assignment problem and its extensions

The quadratic assignment problem (QAP) is a well known combinatorial optimization problem with many applications in computer science and operations research. In this dissertation, we address several aspects of the QAP and some of its extensions. Concerning the QAP, the characterization of a local star minimum is first investigated. Based on this characterization and the underlying network structure of the QAP an extreme point based algorithm is proposed. Then the QAP is reformulated as a constrained linear assignment problem and the possibilities of using this formulation for developing algorithms for the QAP is investigated. A generalization of the QAP formulation is given since the current formulation does not capture the general form of the facility location problem. The characteristics of the new problem are studied and the new formulation is shown to capture the QAP and its generalizations as special cases. In the rest of the dissertation, the focus was on solving a special case of the new problem. This case is termed the Generalized Quadratic SemiAssignment Problem (GQSAP). Several branch and bound algorithms were developed based on the adaptation of the well known Gilmore's bound, and the Relaxation Linearization Technique (RLT) of Sherali and Adams to solve the GQSAP. A set of benchmark problems for this class is obtained by modifying existing Quadratic Assignment benchmark problems.; The results show that the RLT lower bound outperforms the other bounds thus requires a smaller branching tree. On the other hand and due to its high computation time in comparison with the Gilmore's bound, algorithms based on the later performed better in terms of running time. Problems of size up to 22 facilities were solved. The dissertation is concluded with directions for further research.