To lay out or not to lay out?

Abstract

The Quadratic Assignment Problem (QAP) is known as one of the most difficult problems within combinatorial optimization. It is used to model many practical problems including different layout problems. The main topic of this paper is to provide methods to check whether a particular instance of the QAP is a layout problem. An instance is a layout problem if the distances of the objects can be reconstructed on the plane and/or in the 3-dimensional space. A new mixed integer programming model is suggested for the case if the distances of the objects are supposed to be rectilinear distances. If the distances are Euclidean distances then the use of the well-known Multi-Dimensional Scaling (MDS) method of statistics is suggested for reconstruction purposes. The well-known difficulty of QAP makes it a popular and suitable experimental field for many algorithmic ideas including artificial intelligence methods. These types of results are published sometimes as layout problems. The methods of reconstruction can be used to decide whether the topic of a paper is layout or only general QAP. The issue what the OR community should expect from AI based algorithms, is also addressed.