Abstract

The quadratic assignment problem is a well known difficult discrete combinatorial optimization problem. The problem seeks to locate n facilities among n fixed locations in the most economical way. We propose a technique to reduce the number of new constraints and variables in a linearised quadratic assignment problem. It is computationally cheaper to solve a mathematical model with half the number of new constraints and variables than the original full model. The quadratic assignment problem is common in agricultural resource or facility location, economics, production, military operations or operations research in general.

Key words: Linearised quadratic assignment problem, discrete optimization, NP hard, heuristic, lower bound.