Metaheuristics and Heuristics for Global Optimization Problems

点击翻译按钮获取中文摘要

The quadratic assignment problem (QAP) was introduced in 1957 as a mathematical model for the location of a set of indivisible economical activities. Consider the problem of allocating a set of facilities to a set of locations, with the cost being a function of the distance and flow between the facilities, plus costs associated with a facility being placed at a certain location. The objective is to assign each facility to a location such that the total cost is minimized. It was shown that the QAP is NP-hard (Non-deterministic Polynomial-time hard), and that even finding an approximate solution within some constant factor from the optimal solution cannot be done in polynomial time unless P=NP. In fact the QAP, in contrast with its linear counterpart the linear assignment problem, remains one of the hardest optimization problems and no exact algorithm can solve problems of size n > 20. QAP is an example of a global combinatorial optimization, important in operations research and theoretical computer science. Global optimization problems fall within the broader class of nonlinear optimization.