A Distributed Asynchronous Heuristic Algorithm in Generalized Mutual Assignment Problem

DOI Web Site 参考文献18件
  • Hanada Kenta
    Graduate School of Science and Technology, Nara Institute of Science and Technology
  • Amemiya Yuki
    Graduate School of Science and Technology, Nara Institute of Science and Technology
  • Sugimoto Kenji
    Graduate School of Science and Technology, Nara Institute of Science and Technology

抄録

<p>Generalized Mutual Assignment Problem (GMAP) is a multi-agent based distributed combinatorial optimization where the agents try to obtain the most profitable job assignment. Since it is NP-hard problem, it is challenging to achieve feasible solutions of GMAP. Existing algorithms to solve GMAP are synchronous ones, that is, the performance of the entire system would deteriorate if a certain agent takes a long time to solve her own subproblem. Furthermore, topology of communication networks strictly depends on the structure of a given instance due to the way of decomposing the problem into subproblem. In this paper, we propose a novel distributed asynchronous heuristic algorithm based on the Lagrangian decomposition formulation in order to obtain feasible solutions as good as possible. Our proposed algorithm consists of a couple of parts. One is to check the feasibility of candidate feasible solutions and the other is to solve the Lagrangian dual problem to generate a variety of candidates. Both of them are based on asynchronous gossip algorithms which are sometimes introduced for modeling rumor spreading phenomena or calculating an average value of sensors, where only two agents communicate with each other at one iteration. Our experiments show the effectiveness of the proposed method.</p>

収録刊行物

参考文献 (18)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ