Bounded Max-Sum (BMS) is a message-passing algorithm that provides approximation solution to a specific form of de-centralized coordination problems, namely Distributed Constrained Optimization Problems (DCOPs). In particular, BMS algorithm is able to solve problems of this type having large search space at the expense of low computational cost. Notably, the traditional DCOP formulation does not consider those constraints that must be satisfied(also known as hard constraints), rather it concentrates only on soft constraints. Hence, although the presence of both types of constraints are observed in a number of real-world applications, the BMS algorithm does not actively capitalize on the hard constraints. To address this issue, we tailor BMS in such a way that can deal with DCOPs having both type constraints. In so doing, our approach improves the solution quality of the algorithm. The empirical results exhibit a marked improvement in the quality of the solutions of large DCOPs.
翻译:光环 Max-Sum(BMS) 是一种传递信息的算法,它为一种分散式协调问题的具体形式提供了近似的解决办法,即分散式控制优化问题(DCOPs), 特别是, BMS 算法能够解决这类问题,拥有庞大的搜索空间,而以低计算成本为代价。 值得注意的是,传统的 DCOP 配法并不考虑必须满足的制约因素(也称为困难的制约因素),而只是侧重于软约束。 因此,尽管在现实世界的一些应用中观察到这两种类型的制约因素,但BMS 算法并没有积极利用这些困难的制约因素。 为了解决这一问题,我们调整BMS, 以便能与具有两种类型限制的 DCOP 打交道。 在这样做时,我们的方法提高了算法的解决方案质量。 经验结果显示大型 DCOP 解决方案的质量显著提高。