Paper Info
Title
Fast Enumeration Of All Pareto-Optimal Solutions For 0-1 Multi-Objective Knapsack Problems Using Zdds
Abstract
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.
Year
DOI
Venue
2018
10.1587/transfun.E101.A.1375
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
Field
DocType
0-1 multi-objective knapsack problem, ZDD, enumeration, dynamic programming, dominance relation
Enumeration,Theoretical computer science,Pareto optimal,Knapsack problem,Mathematics
Journal
Volume
Issue
ISSN
E101A
9
1745-1337
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Hirofumi Suzuki152.18
Shin-ichi Minato272584.72