Metaheuristics and Heuristics for Global Optimization Problems

二次分配问题（QAP）于1957年被引入，作为一组不可分割的经济活动位置的数学模型。考虑将一组设施分配到一组位置的问题，成本是设施之间的距离和流量的函数，加上与放置在某个位置的设施相关的成本。目标是将每个设施分配到一个位置，以使总成本最小化。结果表明，QAP是NP-难（非确定性多项式时间困难），即使找到一个近似的解决方案，从一些常数因子的最优解不能在多项式时间内完成，除非P=NP。事实上，QAP与其线性对应的线性分配问题相比，仍然是最困难的优化问题之一，并且没有精确的算法可以解决大小n > 20的问题。QAP是全局组合优化的一个例子，在运筹学和理论计算机科学中很重要。全局优化问题属于更广泛的非线性优化类别。

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.