Quadratic Assignment Problem Algorithm Research

Quadratic assignment problem (QAP) is one of the classical NP-hard combinatorialoptimization problems, which is simple to be described but difficult to be solvedoptimally. QAP has not only been applied in various fields, including factory layout, jobshop scheduling, backboard wiring, etc., but also synthesizes a large group of typicalcharacteristics of the problems in combinatorial optimization. QAP is an optimizationproblem with a diversity of applications and important significance of theoretical study.With the enlargement of the scale of QAP instances, the solution space makes thecharacteristic of combinatorial explosion, which therefore can not be solved inpolynomial time. Over the years, owing to its astounding computational complexity, theQAP has drawn the researcher’s attention worldwide in improving the combinatorialoptimization algorithms and methods. Furthermore, the study on the solution methodsfor the QAP plays an important role in the development of itself and the optimizationtechniques.This paper focuses on the solution methods for the QAP based on the linearizationtechniques. To be more specific, which cover:(1) Several dual ascent procedures for thelower bound of the QAP based on Hungarian algorithm are discussed in detail;(2)Three new solution methods are proposed based on making an intensive study on theavailable QAP linearization as well as the QAP lower bound methods;(3) Theresolution of the special kind of QAP in which input matrices there are many zeroelements is further studied, a new solving method, furthermore, is proposed for it;(4)The semi-Lagrangian relaxation of the QAP is proposed, which is a new effectivesolution methods for the QAP.From the theoretical point of view, the results of mathematical derivation in thispaper show that the proposed solution methods for the QAP are feasible. From theexperimental point of view, a few of selected QAP instances in the QAPLIB areimplemented with the new proposed solution methods and some current availablemethods respectively, and the investigated experimental results show that the newproposed solution methods are more important and effective in solving the QAP.