A Distributed Asynchronous Heuristic Algorithm in Generalized Mutual Assignment Problem

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