The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1375-1382

- Publication Date
- 2018/09/01

- Publicized

- 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

Hirofumi SUZUKI

Hokkaido University

Shin-ichi MINATO

Hokkaido University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hirofumi SUZUKI, Shin-ichi MINATO, "Fast Enumeration of All Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack Problems Using ZDDs" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1375-1382, September 2018, doi: 10.1587/transfun.E101.A.1375.

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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1375/_p

Copy

@ARTICLE{e101-a_9_1375,

author={Hirofumi SUZUKI, Shin-ichi MINATO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Fast Enumeration of All Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack Problems Using ZDDs},

year={2018},

volume={E101-A},

number={9},

pages={1375-1382},

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.},

keywords={},

doi={10.1587/transfun.E101.A.1375},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1375

EP - 1382

AU - Hirofumi SUZUKI

AU - Shin-ichi MINATO

PY - 2018

DO - 10.1587/transfun.E101.A.1375

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E101-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2018

AB - 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.

ER -