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

この論文にアクセスする

著者

抄録

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.

収録刊行物

  • 人工知能学会論文誌

    人工知能学会論文誌 31(2), C-F75_1-10, 2016

    一般社団法人 人工知能学会

各種コード

  • NII論文ID(NAID)
    130005126833
  • 本文言語コード
    JPN
  • ISSN
    1346-0714
  • データ提供元
    J-STAGE 
ページトップへ