| Presentation | 2004/11/27 Distributed Lagrangean Relaxation Protocol for the Generalized Mutual Assignment Problem(Artificial Intelligence I)(Joint Workshop of Vietnamese Society of AI, SIGKBS-JSAI, ICS-IPSJ, and IEICE-SIGAI on Active Mining) KATSUTOSHI HIRAYAMA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The generalized assignment problem (GAP) is a typical NP-hard problem and has been studied for many years mainly in the operations research community. The goal of the GAP is to find an optimal assignment of jobs to agents such that the assignment satisfies all of the re-source constraints imposed on individual agents. This work provides a distributed formulation of the GAP, the generalized mutual assignment problem (GMAP), to deal with the problems of task/job assignment in multi-agent systems. Then, we present a distributed lagrangean relaxation protocol that enables the agents to simultaneously solve a GMAP instance without any global control, mechanism nor globally accessible communication medium like shared memory. In the protocol we introduce a parameter that controls the range of "noise" mixed in with the increment/decrement in a lagrangean multiplier. This parameter can be used to make the agents quickly agree on a feasible solution with reasonably good quality. Our experimental results imply that the parameter may also allow you to control a tradeoff between the quality of a solution and the cost of finding it. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | AI2004-31 |
| Date of Issue |
| Conference Information | |
| Committee | AI |
|---|---|
| Conference Date | 2004/11/27(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Distributed Lagrangean Relaxation Protocol for the Generalized Mutual Assignment Problem(Artificial Intelligence I)(Joint Workshop of Vietnamese Society of AI, SIGKBS-JSAI, ICS-IPSJ, and IEICE-SIGAI on Active Mining) |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | KATSUTOSHI HIRAYAMA |
| 1st Author's Affiliation | Faculty of Maritime Sciences, Kobe University() |
| Date | 2004/11/27 |
| Paper # | AI2004-31 |
| Volume (vol) | vol.104 |
| Number (no) | 485 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |