情報処理学会 第79回全国大会講演要旨

多目的組合せ問題では、パレート解と呼ばれるある種の最適性を持つ解を探し出す手法が用いられる。一般にパレート解は複数存在し、それらを列挙することは応用上有効である。0-1多目的ナップサック問題に対して、動的計画法に基づきパレート解を列挙する手法がBazganらにより提案されている。一方で、組合せ問題へのアプローチに有効なデータ構造としてZDDが知られいる。ZDDは組合せ問題の実行可能解列挙、および索引化などに威力を発揮する。本稿では、ZDDを用いてBazganらの手法を改良・高速化し、なおかつ列挙された解を索引化する手法を提案する。