過制約な一般化相互割当問題に対する分散ラグランジュ緩和プロトコル

• Item type: Journal(1)
• 公開日: 2012-11-15
• タイトル: 過制約な一般化相互割当問題に対する分散ラグランジュ緩和プロトコル
• タイトル / 言語: en
• タイトル: Distributed Lagrangian Relaxation Protocol for the Over-constrained Generalized Mutual Assignment Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：エージェントの理論とその応用] 一般化相互割当問題，分散最適化，ラグランジュ緩和
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 神戸大学海事科学研究科
• 著者所属: 神戸大学海事科学研究科
• 著者所属(英): en
• 著者所属(英): Kobe University
• 著者所属(英): en
• 著者所属(英): Kobe University
• 著者名: 花田, 研太; 平山, 勝敏
• 著者名(英): Hanada, Kenta; Hirayama, Katsutoshi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 一般化相互割当問題（GMAP）において，エージェントの資源容量が著しく少ない過制約な問題を解く手法を2つ提案する．1つは，割り当てられない財をすべて引き受けるdisposalエージェントを新たに加え，標準のGMAPとして解く手法，もう1つは割当制約を不等式として記述し問題を解く手法である．エージェントの資源容量を加工した一般化割当問題（GAP）のベンチマーク問題例を上記両手法で解き，得られたデータを比較，考察した．その結果，前者の方法は過制約度の低い問題例に対して，後者の方法は過制約度の高い問題例に対して有効であることが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Generalized Mutual Assignment Problem (GMAP) is a distributed combinatorial optimization problem in which, with no centralized control, multiple agents search for an optimal assignment of goods that satisfies their individual knapsack constraints. Previously, in the GMAP protocol, problem instances were assumed to be feasible, meaning that the total capacities of the agents were large enough to assign the goods. However, this assumption may not be realistic in some situations. In this paper, we present two methods for dealing with such “over-constrained” GMAP instances. First, we introduce a disposal agent who has an unlimited capacity and is in charge of the unassigned goods. With this method, we can use any off-the-shelf GMAP protocol since the disposal agent can make the instances feasible. Second, we formulate the GMAP instances as an Integer Programming (IP) problem, in which the assignment constraints are described with inequalities. With this method, we need to devise a new protocol for such a formulation. We experimentally compared these two methods on the variants of Generalized Assignment Problem (GAP) benchmark instances. Our results indicate that the first method finds a solution faster for fewer over-constrained instances, and the second finds a better solution faster for more over-constrained instances.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 53, 号 11, p. 2370-2378, 発行日 2012-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764