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

Hirofumi SUZUKI  Shin-ichi MINATO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1375-1382
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1375
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
0-1 multi-objective knapsack problem,  ZDD,  enumeration,  dynamic programming,  dominance relation,  

Full Text: PDF(967.5KB)
>>Buy this Article


Summary: 
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.