分散ラグランジュ緩和プロトコルにおけるバンドル法  [in Japanese] A Bundle Method in Distributed Lagrangian Relaxation Protocol  [in Japanese]

Access this Article

Author(s)

Abstract

The <i>Generalized Mutual Assignment Problem</i> (GMAP) is a maximization problem in distributed environments, where multiple agents select goods under resource constraints. <i>Distributed Lagrangian Relaxation Protocols</i> (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 <i>subgradient method</i> to explore a better upper bound by updating the <i>Lagrange multipliers (prices)</i> 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 <i>Bundle Method</i> and refer to it as <i>Bundle DisLRP</i> (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

Codes

  • NII Article ID (NAID)
    130005126833
  • Text Lang
    JPN
  • ISSN
    1346-0714
  • Data Source
    J-STAGE 
Page Top