A Bundle Method in Distributed Lagrangian Relaxation Protocol
-
- Hanada Kenta
- Graduate School of Maritime Sciences, Kobe University
-
- Hirayama Katsutoshi
- Graduate School of Maritime Sciences, Kobe University
-
- Okimoto Tenda
- Graduate School of Maritime Sciences, Kobe University
Bibliographic Information
- Other Title
-
- 分散ラグランジュ緩和プロトコルにおけるバンドル法
Abstract
The Generalized Mutual Assignment Problem (GMAP) is a maximization problem in distributed environments, where multiple agents select goods under resource constraints. Distributed Lagrangian Relaxation Protocols (DisLRP) are peer-to-peer communication protocols for solving GMAP instances. In DisLRPs, agents seek a good quality upper bound for the optimal value by solving the Lagrangian dual problem, which is a convex minimization problem. Existing DisLRPs exploit a subgradient method to explore a better upper bound by updating the Lagrange multipliers (prices) of goods. While the computational complexity of the subgradient method is very low, it cannot detect the fact that an upper bound converges to the minimum. Moreover, solution oscillation sometimes occurs, which is one of the critical issues for the subgradient method. In this paper, we present a new DisLRP with a Bundle Method and refer to it as Bundle DisLRP (BDisLRP). The bundle method, which is also called the stabilized cutting planes method, has recently attracted much attention as a way to solve Lagrangian dual problems in centralized environments. We show that this method can also work in distributed environments. We experimentally compared BDisLRP with Adaptive DisLRP (ADisLRP), which is a previous protocol that exploits the subgradient method, to demonstrate that BDisLRP performed convergence faster with better quality upper bounds than ADisLRP.
Journal
-
- Transactions of the Japanese Society for Artificial Intelligence
-
Transactions of the Japanese Society for Artificial Intelligence 31 (2), C-F75_1-10, 2016
The Japanese Society for Artificial Intelligence
- Tweet
Details 詳細情報について
-
- CRID
- 1390282680083668736
-
- NII Article ID
- 130005126833
-
- ISSN
- 13468030
- 13460714
-
- Text Lang
- ja
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed