[4K2-OS-16b] AI における離散構造処理と制約充足(2)

[4K2-OS-16b-03] ZDD を用いた種々のネットワーク設計問題の解法

〇鈴木 浩史¹、石畠 正和¹、湊 真一¹ (1. 北海道大学　大学院情報科学研究科)

キーワード：ネットワーク設計問題、ZDD、制約充足

ネットワーク設計は運送や通信など様々なサービスやシステムにおける重要な課題であり，グラフ構造を用いてネットワーク設計問題として定式化されている．ネットワーク設計問題は，候補グラフ集合と制約が与えられたとき制約を満たす目的グラフを見つける問題である．いくつかの代表的な制約に対しては，多くのアルゴリズムが提案されてきた．しかし，応用にあたって，より一般的な制約や数式的に記述できない制約が要求された場合，既存のアルゴリズムでは不十分である．そこで我々は，ネットワーク設計問題に対する統一的な手法を提案し，様々な制約における目的グラフ集合を求めることで適切な目的グラフの選択をサポートすることを狙う．提案手法は目的グラフ集合を集合族の演算により記述する．また，実際に演算を処理するために，集合族を圧縮処理するデータ構造Zero-suppressed Binary Decision Diagrams (ZDDs) を用いる．ベンチマークのグラフを用いて，様々な制約に提案手法を適用した結果，現実的な時間で目的グラフ集合を求めることに成功した．