講演抄録/キーワード |
講演名 |
2018-11-05 15:10
[ポスター講演]劣モジュラ関数最大化問題に対する効率的な分枝限定法 ○植松直哉・梅谷俊治・河原吉伸(阪大/理研) IBISML2018-68 |
抄録 |
(和) |
しかし,特徴抽出やセンサ配置問題など厳密な最適解やより良い近似解が必要となる応用事例も少なくない.
本研究では,多数の制約式をともなう整数計画問題の定式化に基づく分枝限定法を提案する.
NemhauserとWolseyは一部の制約式からなる緩和問題から始め,緩和問題を解いては新しい制約式を1つ加える手続きを繰り返す制約生成法(constraint generation algorithm)を提案した.
しかし,彼らの手法では多数の緩和問題を解く必要があり,多大な計算時間を要することが知られている.
本研究では,各反復で効果的な制約式の集合を加えることで,少数の緩和問題を解くだけで最適値の良い上界を得る改良制約生成法(improved constraint generation algorithm)を提案し,これを分枝限定法に組み込んだ.
代表的なベンチマーク問題例に対する数値実験により,提案手法が従来手法より良い性能を示すことを確認した. |
(英) |
The submodular function maximization is an attractive optimization model that appears in many real applications.
Although a variety of greedy algorithms quickly find good feasible solutions for many instances while guaranteeing $(1-1/e)$-approximation ratio.
In this paper, we propose an efficient branch-and-bound algorithm for the submodular maximization problem based on solving binary integer programming problems.
We also show that our algorithms achieved better performance than the state-of-the-art exact algorithms for well-known benchmark instances. |
キーワード |
(和) |
劣モジュラ関数最大化 / 分枝限定法 / 列生成法 / 整数計画問題 / / / / |
(英) |
submodular function maximization / branch-and-bound algorithm / column generation method / integer programming problem / / / / |
文献情報 |
信学技報, vol. 118, no. 284, IBISML2018-68, pp. 183-190, 2018年11月. |
資料番号 |
IBISML2018-68 |
発行日 |
2018-10-29 (IBISML) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IBISML2018-68 |