几乎最快与渐近最优的并行分枝界限算法(英文)

A Nearly Fastest and Asymptotically Optimal General Parallel Branch and Bound Algorithm

分枝界限算法是求解组合优化问题的技术之一 ,它被广泛地应用在埃运筹学与组合数学中 .对共享存储的最优优先一般并行分枝界限算法给出了运行时间复杂度下界Ω ( m / p +hlogp ) ,其中 p为可用处理器数 ,h为扩展的结点数 ,m为状态空间中的活结点数 .通过将共享存器设计成 p个立体堆 ,提出了 PRA M- EREW上一个新的一般并行分枝界限算法 ,理论上证明了对于 h<p2 p ,该算法为最快且渐近最优的并行分枝界限算法 .最后对 0 -

Branch and Bound (B&B) is a problem solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. In this paper, the lower bound of running time Ω(m/p+h log p) (the base of all logarithms in this paper is 2) is presented for general parallel best first B&B algorithms on shared memory systems, where p is the number of processors available, h is the number of expanded nodes, and m is the total number of active nodes in state space tree. In addition, a new general parallel best first B&B algorithm on PRAM EREW is proposed by devising the shared memory into p cubeheaps. Theoretical analysis shows that it is the fastest algorithm for h<p·2 p , and it is asymptotically optimal in this type of general parallel B&B algorithms. Computational experiments are conducted to solve 0-r knapsack problem.