Content area
The following nonlinear assignment problems (NAPs) are examined in this dissertation: quadratic assignment problem (QAP), biquadratic assignment problem (BiQAP), turbine balancing problem (TBP), and multidimensional assignment problem (MAP). All of the above are NP-hard combinatorial optimization problems that are natural extensions of the classical linear assignment problem. NAPs have numerous applications in different fields, ranging from the assignment of facilities to sites in location theory, to the tracking of elementary particles in high energy physics. In this dissertation we present heuristic algorithms for solving the above NAPs.
The dissertation is divided into three parts. In the first part, a survey of nonlinear assignment problems is presented, with focus on the most studied, QAP. Different formulations, complexity, lower bounds, exact and heuristic solution methods, and essentially all aspects that have been studied for these problems are presented.
The second part presents heuristic algorithms for solving sparse QAP instances, the BiQAP and the TBP. Sparse QAP instances are those whose input matrices contain a large fraction of zeroes. We present a heuristic algorithm that exploits the sparsity of such instances, and provides approximate solutions. The TBP is formulated as a QAP, and an algorithm that outperforms the current industry practice is presented. The BiQAP is an assignment problem where the objective function is a fourth-degree multivariable polynomial. We propose a heuristic algorithm for solving the BiQAP, and computational results on instances described in the literature indicate that it consistently finds better solutions than previously described algorithms.
In the third part, heuristic algorithms for solving the MAP and its special case the three-dimensional assignment problem are presented. The multi-target multi-sensor tracking problem (MTMST) which has applications in military tracking systems and in high energy physics is examined, and we show how the MTMST can be formulated as an MAP. A heuristic algorithm that solves the MAP is described, and it is tested on a set of problems provided by the US Air Force.
Computational results indicate that all of the suggested algorithms are among the best in the literature in terms of solution quality and computational time.