[4P2-OS-17b] 数理最適化

[4P2-OS-17b-05] 大規模な2値整数計画問題に対する効率的な重み付き局所探索法

〇梅谷 俊治¹ (1. 株式会社リクルート)

キーワード：組合せ最適化、整数計画、メタヒューリスティクス

大規模な2値整数計画問題において、局所探索法の探索空間を削減するデータマイニングの手法を提案する。大規模な近傍探索は局所最適解の品質を向上させるが、同時に計算時間も指数関数的に増加する。この課題を解決するために、多くの研究者は、個々の問題の定式化から効率的な近傍探索に有用な特徴を発見してきた。しかし、2値整数計画問題は汎用性が高いため、その定式化はアルゴリズムの性能向上に役立つ特徴がほとんど持たない。
本研究では、（問題の定式化ではなく）現在解くべき入力データから、近傍探索において同時に反転する変数の有望な組を特定するための変数の関連性を抽出する。これに基づき、解の増分評価とペナルティ重みの適応的制御を組み込んだ4反転近傍局所探索を開発する。
大規模な集合被覆問題と集合分割問題に対する数値実験の結果より、提案手法が局所探索法の性能を改善したことを確かめた。