[1N1-GS-5] Agents: basic theory

[1N1-GS-5-04] ADMM-based Price Update in Generalized Mutual Assignment Problem

〇Kenta Hanada¹, Yuki Amemiya¹, Kenji Sugimoto¹ (1. Nara Institute of Science and Technology)

Keywords:multi-agent system, distributed combinatorial optimization, generalized mutual assignment problem, heuristic algorithm, alternating direction method of multiplier

We aim to obtain feasible solutions of Generalized Mutual Assignment Problem (GMAP) as good as possible in a distributed environment (multi-agent system). In existing studies, distributed Lagrangian heuristic algorithms have been proposed where the agents try to find feasible solutions based on prices (Lagrange multipliers), and it is known that good quality feasible solutions can be obtained by updating the price based on the solution of the convex optimization problem (Lagrangian dual problem). In this study, we introduce Alternating Direction Method of Multiplier (ADMM) as an algorithm for updating prices. ADMM is an algorithm to solve convex optimization problems in a distributed environment with a proximal operator (mapping). However, the proximal mapping cannot be calculated easily due to the black box of the objective function in the Lagrangian dual problem. Therefore, the proximity mapping is calculated by linear approximation of the objective function. The effectiveness of the proposed algorithm is evaluated by numerical experiments.