
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Fast Enumeration of All ParetoOptimal Solutions for 01 MultiObjective Knapsack Problems Using ZDDs
Hirofumi SUZUKI Shinichi MINATO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E101A
No.9
pp.13751382 Publication Date: 2018/09/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E101.A.1375
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: 01 multiobjective knapsack problem, ZDD, enumeration, dynamic programming, dominance relation,
Full Text: PDF(967.5KB) >>Buy this Article
Summary:
Finding Paretooptimal solutions is a basic approach in multiobjective combinatorial optimization. In this paper, we focus on the 01 multiobjective knapsack problem, and present an algorithm to enumerate all its Paretooptimal 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 zerosuppressed 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 Paretooptimal solutions. The results of our experiments show that our algorithm is faster than the previous method for various types of three and fourobjective instances, which are difficult problems to solve.

