Fast Enumeration of All Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack Problems Using ZDDs

DOI Web Site 参考文献12件
  • SUZUKI Hirofumi
    Graduate School of Information Science and Technology, Hokkaido University
  • MINATO Shin-ichi
    Graduate School of Information Science and Technology, Hokkaido University

書誌事項

公開日
2018-09-01
資源種別
journal article
DOI
  • 10.1587/transfun.e101.a.1375
公開者
一般社団法人 電子情報通信学会

この論文をさがす

説明

<p>Finding Pareto-optimal solutions is a basic approach in multi-objective combinatorial optimization. In this paper, we focus on the 0-1 multi-objective knapsack problem, and present an algorithm to enumerate all its Pareto-optimal solutions, which improves upon the method proposed by Bazgan et al. Our algorithm is based on dynamic programming techniques using an efficient data structure called zero-suppressed binary decision diagram (ZDD), which handles a set of combinations compactly. In our algorithm, we utilize ZDDs for storing all the feasible solutions compactly, and pruning inessential partial solutions as quickly as possible. As an output of the algorithm, we can obtain a useful ZDD indexing all the Pareto-optimal solutions. The results of our experiments show that our algorithm is faster than the previous method for various types of three- and four-objective instances, which are difficult problems to solve.</p>

収録刊行物

参考文献 (12)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ