关键词：对等方式；B＆B算法；分布式算法；通信
摘 要：In this chapter, we proposed a new peer-to-peer approach for the tree-based B&B algorithm. This approach is based on fully distributed algorithms dealing with work sharing and termination detection in an asynchronous FIFO message passing communication model. Using a small-degree, small-diameter network overlay, we argued that this approach allows us to improve the scalability of the state-of-the-art master-slave approach by controlling the overhead in terms of message exchanged and increasing the overall parallel efficiency. We also show by extensive experiments that our P2P approach effectively scales well and induces significant improvements to the the master-slave approach. Although our algorithms were discussed in the specific context of permutation-based problems and parallel B&B, it is not difficult to see that it can be extended to other contexts. Roughly speaking, for that purpose one must define the following features depending on the application context: (ⅰ) an encoding of work units (intervals), (ⅱ) the processing of work units (sequential B&B), and (ⅲ) the global information that needs to be shared (best B&B solution).