2020/12/02 by Md. Musfiqur Rahman, Mashrur Rashik, Rahman, Md. Musfiqur +5
Computer Science · Engineering · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #Data Management and Algorithms #FOS: Computer and information sciences #Multiagent Systems (cs.MA) #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2012.01369
openalex publication_date 2020/12/02 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Bounded Max-Sum (BMS) is a message-passing algorithm that provides\napproximation solution to a specific form of de-centralized coordination\nproblems, namely Distributed Constrained Optimization Problems (DCOPs). In\nparticular, BMS algorithm is able to solve problems of this type having large\nsearch space at the expense of low computational cost. Notably, the traditional\nDCOP formulation does not consider those constraints that must be\nsatisfied(also known as hard constraints), rather it concentrates only on soft\nconstraints. Hence, although the presence of both types of constraints are\nobserved in a number of real-world applications, the BMS algorithm does not\nactively capitalize on the hard constraints. To address this issue, we tailor\nBMS in such a way that can deal with DCOPs having both type constraints. In so\ndoing, our approach improves the solution quality of the algorithm. The\nempirical results exhibit a marked improvement in the quality of the solutions\nof large DCOPs.\n