Improving Solution Quality of Bounded Max-Sum Algorithm to Solve DCOPs involving Hard and Soft Constraints
This work provides an incremental improvement for researchers and practitioners working with DCOPs that involve both hard and soft constraints, enhancing the applicability of the BMS algorithm.
The paper addresses the limitation of the Bounded Max-Sum (BMS) algorithm in handling hard constraints within Distributed Constrained Optimization Problems (DCOPs). By tailoring BMS to incorporate both hard and soft constraints, the authors demonstrate a marked improvement in the solution quality for large DCOPs.
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.