ADMM-based Price Update in Generalized Mutual Assignment Problem

DOI

Bibliographic Information

Other Title
  • 一般化相互割当問題に対する交互方向乗数法を用いた価格更新

Abstract

<p>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.</p>

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top