Modelling a Clustered Generalized Quadratic Assignment Problem

Publication, 2015


J. Fechter, A. Beham, S. Wagner, M. Affenzeller - Modelling a Clustered Generalized Quadratic Assignment Problem - Proceedings of the 27th European Modeling and Simulation Symposium EMSS 2015, Bergeggi, Italy, 2015, pp. 7


This paper is about the modelling of an assignment problem motivated by a real world problem instance. We consider multiple pieces of equipment which need to be assigned to several locations taking into account capacities as well as relations between equipment and distances between locations. Additionally, a clustering of locations is taken into account that groups locations into areas or fields. It is forbidden to assign the same equipment to locations in different fields. The problem arises in many real world applications such as facility layout or location problems. We discuss the complexity of the problem and prove its NP-hardness. Further two linearization approaches are presented as well as computational studies of the original and the linearized models are conducted. Experimental tests are carried out using CPLEX.