TCS-TR-A-17-81

Date: Thu Jun 1 17:25:12 2017

Title: ZDD-Based Enumeration of Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack Problems

Authors: Hirofumi Suzuki and Shin-ichi Minato

Contact:

First name: Shin-ichi
Last name: Minato
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060- 0814, Japan
Email: minato@ist.hokudai.ac.jp

Abstract. Finding pareto-optimal solutions is a basic approach in multi-objective combinatorial optimization. In this paper, we focus on 0-1 multi-objective knapsack problems, and present an algorithm to enumerate all pareto-optimal solutions of them, inspired by (Bazgan, Hugot, and Vanderpooten, Computers and OR, 36(1):260{279, 2009). Our algorithm is based on dynamic programming techniques using an efficient data structure, called zero-suppressed binary decision diagram (ZDD), which handles set of combinations compactly. In our algorithm, we utilize ZDDs for pruning inessential partial solutions. As an output of the algorithm, we can obtain a useful ZDD indexing all pareto-optimal solutions. The results of our experiments showed that our algorithm is clearly faster than previous method in several three-objective and four-objective instances, which are harder problems to be solved.