黑白二次分配问题

Black and White Quadratic Assignment Problem

二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑色设备的距离不超过预定阈值.文章将之定义为黑白二次分配问题BWQAP(Black and White QAP).文章首先分析了它的计算复杂性,指出该问题是NP-难解问题,不存在ε-近似度的多项式时间近似算法(ε>0).同时证明了其可行解的存在性与黑白图上的支配集问题等价,也属于NP-难解问题.为了能在可接受的时间内得到大规模实例质量可接受的近似解,提出了一种求解BWQAP的启发式算法GFO.该算法利用QAP现有算法得到初始解,然后利用局部搜索策略完成解的可行化和优化.大量实验表明,该启发式算法能够有效地求解BWQAP问题的实例.

Research on variants of the QAP （Quadratic Assignment Problem） has become a hot line in this area. There exists a new kind of problem in applications which can＇t be modeled as a QAP or its variants. The facility set is partitioned into sets of black and white facilities, and extra constraints are added to the QAP： Every white facility must be less than a predefined distance away from at least one black facility. The new problem is modeled as the black and white QAP （BWQAP） in this paper. It is indicated that the BWQAP is NP-Hard and there is no ε-approximation algorithm for it （ε〉0）, furthermore, it is that it is also NP-Hard to determine whether a feasible solution exists by proving its equivalence to dominating sets on black and white graph. A new heuristics-GFO is then presented to obtain high quality solutions for large scale instances in reasonable time. The GFO employs existing algorithms for the QAP to obtain an initial solution, then applies local search to gain feasibility and optimization. Experiments on a great number of instances had shown that the new heuristic was effective and efficient to solve the BWQAP.