Heuristic algorithms for the quadratic semi-assignment problem

A particular problem of assigning several activities on a limited number of facilities is considered; each activity has to be assigned to one facility and every combination of two activities scheduled on the same facility implies an interaction cost. The sum of all the interaction costs, over all the pair of activities assigned to the same facility, has to be minimized. This problem can be formulated as an integer quadratic semi-assignment problem and is shown to be NP-hard. For its solution, heuristic procedures are here proposed, which are modifications and improvements of two algorithms known in literature. Theoretical results are also shown for the evaluation of the complexity of the new heuristics; finally a wide computational experience is reported.