文献

J-GLOBAL ID：202102279212847192   整理番号：21A0332081

コスト制約つき組合せ問題に対するZDDを用いた高速な解列挙手法

A Fast ZDD-Based Method for Enumerating All Solutions of Cost-Bounded Combinatorial Problems

著者 (7件)： 湊真一 (京大 大学院情報学研究科) ,  番原睦則 (名古屋大 大学院情報学研究科) ,  堀山貴史 (北大 大学院情報科学研究院) ,  川原純 (京大 大学院情報学研究科) ,  瀧川一学 (理研 革新知能統合研究セ(AIP)) ,  瀧川一学 (北大 化学反応創成研究拠点(ICReDD)) ,  山口勇太郎 (九大 大学院システム情報科学研究院)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 120  号： 276(COMP2020 18-27)  ページ： 8-15 (WEB ONLY)  発行年： 2020年11月27日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフの最短路問題のように,組合せ問題のアイテムにコストが定義されているときに,コスト総和が所与の閾値以下となるような実行可能解を列挙することは,多くの実用的な応用を持つ汎用的で重要な問題である。この問題はコスト数値の有効桁数が大きいと急激に計算量が増大する。本研究では,このような一般的なコスト制約つき組合せ問題に対して,ZDD(Zero-suppressed Binary Decision Diagram)を用いて大量の解を高速に全列挙する手法を提案する。実験の結果,実用的な規模の例題に対して,数百万通りの解集合を表すZDDを1秒以内で構築することができた。本手法は多数の解を列挙する場合に従来手法より圧倒的に高速であり,様々な応用が期待される。(著者抄録)

シソーラス用語： *組合せ問題 ,  *二分決定グラフ ,  計算量 ,  制約条件 ,  *論理プログラミング
準シソーラス用語： *ZDD ,  *解集合プログラミング

分類 (1件)： 数値計算  (JE02000J)

引用文献 (12件)：

• “Ibm ilog cplex optimization studio v12.10.0 documentation”, https://www.ibm.com/jp-ja/products/ilog-cplex-optimization-studio/ (2019).
• “Gurobi optimization: Gurobi optimizer reference manual version 9.1”, https://gurobi.com/ (2020).
• “Sugar: a sat-based constraint solver”, http://bach.istc.kobe-u.ac.jp/sugar/ (2018).
• K. Wasa: “Enumeration of enumeration algorithms”, CoRR,abs/1605.05102, (2016).
• 湊真一(編):“超高速グラフ列挙アルゴリズム-〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ-”, 森北出版(2015).

タイトルに関連する用語 (4件)： 制約 ,  組合せ問題 ,  ZDD ,  解列