TCS -TR-A-17-81

TCS Technical ReportZDD-Based Enumeration of Pareto-Optimal Solutions
for 0-1 Multi-Objective Knapsack Problems
byHirofumi Suzuki and Shin-ichi Minato

Division of Computer Science
Report Series A
June 1, 2017

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

h-suzuki@ist.hokudai.ac.jp

Phone:+81-011-706-6471

Fax:+81-011-706-6471

ZDD-Based Enumeration of Pareto-Optimal Solutions
for 0-1 Multi-Objective Knapsack Problems
Hirofumi Suzuki

Shin-ichi Minato

Grad. School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060–0814, Japan

Grad. School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060–0814, Japan

June 1, 2017

(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 & OR,
36(1):260–279, 2009). Our algorithm is based on dynamic programming techniques
using an eﬃcient 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 ourexperiments showed that our algorithm is clearly faster than previous method inseveral three-objective and four-objective instances, which are harder problems tobe solved.

1

Introduction

In multi-objective combinatorial optimization, eﬃcient solutions have the property
called pareto-optimality, that any objective can not be improved whithout changing
other objective for the worse. A solution with the pareto-optimality is called paretooptimal solution. Several results and annotated bibliographies of multi-objective
combinatorial optimization can be found in [7].
In this paper, we focus on the 0-1 multi-objective knapsack problem which is theone of multi-objective combinatorial optimization problems. The single-objective
version of this problem is well-studied in the literature [6]. Multi-objective cases
have many practical applications for example capital budgeting [10], and selecting
transportation investment alternatives [11].
To find a reduced set or the complete set of pareto-optimal solutions is a typicalapproach in multi-objective combinatorial optimization. In the 0-1 multi-objective1

2

Hirofumi Suzuki and Shin-ichi Minato

knapsack problem, metaheuristics are better to find an approximately reduced set
in many cases [5] [12]. Only for the bi-objective case, labeling algorithm [4] andϵ-constraint method [3] can find the complete set. For general cases, the dynamic
programming and some pruning based approach has been proposed [1]. Bazgan etal. showed that their approach is faster than labeling algorithm and ϵ-constraint
method in bi-objective cases. Moreover, they conducted experiments to find thecomplete set in three-objective cases.
In this paper, we propose a more practical algorithm to find the complete set ofpareto-optimal solutions inspired by the Bazgan’s approach. The algorithm uses
an eﬃcient data structure, named zero-suppressed binary decision diagram (ZDD),
which can index a huge number of combinations in compact form [8]. There aremany practical applications of ZDDs in combinatorial optimization problems including the single-objective knapsack problem [2] [9]. We designed pruning heuristics using ZDDs which indexes all feasible solutions. It is more accurate thanconventional methods. In addition, we can get the useful ZDD indexing all thepareto-optimal solutions as the output of our algorithm.
We conducted computational experiments to compare Bazgan’s algorithm andour algorithm. The results of computation time showed that our algorithm isclearly faster than Bazgan’s algorithm for various types of three-objective and fourobjective instances, which are harder problems to be solved. We also investigatedthe compression eﬃciency of output ZDDs.
This paper is organized as follows. In section 2, we formally define the 0-1 multiobjective knapsack problem and describe ZDDs. Section 3 presents the frameworkof our algorithm. Pruning conditions using our algorithm are described in section 4.
Section 5 presents the algorithmic issues. Computational experiments and results
are reported in section 6. In section 7, we conclude this paper.

2

Preliminaries

2.1

0-1 Multi-objective Knapsack Problem

The 0-1 multi-objective knapsack problem is known as one of multi-objective combinatorial optimization problems. Given n items I = {1, . . . , n} and an integercapacity C > 0. In m-objective cases, each item i ∈ I has an integer weighti ).
wi > 0, and a m-dimensional non-negative integer-valued vector v i = (v1i , . . . , vm
A solution of the problem is a combination of items X ⊆ I. The total weight of a∑solution X is denoted by w(X) = i∈X wi . If X is a feasible solution, it satisfies
w(X) ≤ C. We define the set of all the feasible solutions X = {X ⊆ I|w(X) ≤ C}.
The value of a solution X is denoted by the sum of the valued vectors v(X) =i
i∈X v . Let us define the order relation < on valued vectors as follows:{ai ≤ bi , ∀i ∈ {1, . . . , m}, anda < b ⇐⇒
(1)
aj < bj , ∃j ∈ {1, . . . , m}.

∑

ZDD-Based Enumeration of Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack ...

3

We also define a partial order relation ∆ on X , called dominance relation, using
the order relations < as follows:∀X, X ′ ∈ X , X∆X ′ ⇐⇒ v(X) < v(X ′ ).

(2)

If X∆X ′ , we say that X is dominated by X ′ or X ′ dominates X. On the dominancerelation, a solution X ∈ X is called pareto-optimal solution, if X is not dominatedby any feasible solution X ′ ∈ X . Let P be the set of all the pareto-optimal
solutions. A typical goal of the problem is to find a reduced set P ′ ⊆ P or thecomplete set P. In this paper, our goal is to find the complete set P.

2.2

Zero-suppressed Binary Decision Diagram

Zero-suppressed binary decision diagram (ZDD) is a data structure to represent
a set of combinations in compact form. A ZDD is a directed acyclic graph Z =(N , A) with node set N and arc set A. It has two terminal nodes ⊤ and ⊥.
Each non-terminal node α ∈ N has two arcs 0-arc and 1-arc. A node pointed by
x-arc of α is denoted by αx , and called x-child of α. A ZDD has a root node ρwhich is not pointed by any arcs. In 0-1 multi-objective knapsack problems, wemanipulate the set of items I with ordering as 1 < . . . < n. Each non-terminal
node α ∈ N has a label ℓ(α) ∈ I where ℓ(α) < ℓ(αx ) (x ∈ {0, 1}). We supposethat ℓ(⊤) = ℓ(⊥) = n + 1 for convenience.
A path from a node α to the terminal ⊤ represents a combination X ⊆ I. Itemi ∈ I belongs to X iﬀ the path has a 1-arc which goes out a node labeled with i.
We define the set of combinations represented by a node α ∈ N as follows:
X (α) = {X ⊆ I | A path α to ⊤ corresponds to X}.

(3)

Especially, X (ρ) is the whole set represented by Z.
ZDDs can be reduced by the following two rules.
1. Share any isomorphic subgraphs.
2. Delete all nodes whose 1-arc points ⊥.
We can use the above two rules in any order. Then the form of the ZDD is uniquelydetermined, and we call it irreducible ZDD (show Fig. 1). We suppose that ZDD
is irreducible unless otherwise noted. Note that any irreducible ZDD for X has noarc which points ⊥, and we can construct it in O(nC) time [2].

3

Framework of Dynamic Programming over ZDDs

3.1

Basic Concept

Let Z = (N , A) be the ZDD with a root node ρ where X (ρ) = X . Then we try
to extract the set P from Z by the dynamic programming (DP). In the DP, we4

Hirofumi Suzuki and Shin-ichi Minato

Figure 1: An example of ZDD for a 0-1 multi-objective knapsack problem

manage sets of states corresponding to feasible solutions. A state s consists of am-dimentional valued vector s.v and a node s.α ∈ N .
The DP consists of n phases. Let Si be a set of states that each state s ∈ Si
satisfies ℓ(s.α) = i + 1. Then Si corresponds to a set of solutions consisting of thefirst i items {1, . . . , i}. Initially, let S0 = {sϕ } where sϕ .v = 0, and sϕ .α = ρ. It
represents the empty knapsack. At the phase i we extend all the states s ∈ Si−1
as follows: For all b ∈ {0, 1}, we generate a state sb where sb .v = s.v + b × v i , andsb .α = s.αb . After that sb is added to the set of states Sj where j = ℓ(sb .α) − 1.
Note that, it is not necessary to maintain the capacity, because all the transitions
on Z generate a feasible solution.
In this process, many states will not become any pareto-optimal solution. Thus
we conduct a pruning of them as much as possible for obtaining Sn which corresponds to P.

3.2

Pruning Condition

Because of the property that X (ρ) = X , the set of all the combinations of items
which can be added to a state s without violation is represented by X (s.α). Let us
define the set of valued vectors E(s) = {s.v + v(X) | X ∈ X (s.α)}. It corresponds
to the set of all the feasible solutions extended from s.
The pruning process uses d relations ∆1 , . . . , ∆d which is similar to the dominance relation. Each relation ∆k (k = 1, . . . , d) must have the following property:∀s, s′ ∈ Si (i = 1, . . . , n), s∆k s′ ⇒ ∀e ∈ E(s), ∃e′ ∈ E(s′ ), e < e′ .

(4)s∆k s′ means that all the feasible solutions extended from s is dominated by anothersolution extended from s′ . We call such relations as future dominance relation.
According to the d future dominance relations, we can conduct a pruning as follows:
For a state s ∈ Si , if there is a state s′ ∈ Si and an integer k ∈ {1, . . . , d} wheres∆k s′ , we delete s from Si .
When at least one relation ∆k satisfies∀s, s′ ∈ Sn , s∆k s′ ⇐⇒ s.v < s′ .v,(5)

ZDD-Based Enumeration of Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack ...

5

Sn becomes the set of valued vectors of P. In the next section, we define two future
dominance relations used in our algorithm.

4

Future Dominance Relations Using ZDDs

4.1

Relation Based on Implicit Capacities

The first future dominance relation is based on the following observation. For two
states s, s′ ∈ Si (i = 1, . . . , n), we suppose that s.v < s′ .v and X (s.α) ⊆ X (s′ .α).
For all X ∈ X (s.α), e = s.v +v(X) ∈ E(s). Also, e′ = s′ .v +v(X) ∈ E(s′ ), because
X ∈ X (s′ .α). Then e < e′ . This situation matches the condition (4). Thus wedefine the future dominance relation ∆c on Si (i = 1, . . . , n) by:∀s, s′ ∈ Si , s∆c s′ ⇐⇒ s.v < s′ .v, and X (s.α) ⊆ X (s′ .α).

(6)∆c also satisfies (5), because X (s.α) = X (s′ .α) = X (⊤) = ϕ for i = n.
We can check X (s.α) ⊆ X (s′ .α) easily as follows: For a node α, let us define
the maximum weight on X (α) as c(α) = max{w(X) | X ∈ X (α)}. Then c(s.α)
denotes the remaining capacity of a state s implicitly. Therefore c(s.α) ≤ c(s′ .α)and X (s.α) ⊆ X (s′ .α) are equivalent. For calculating c(α), we can use the recursion
formula defined by:c(⊤) = 0, c(α) = max{c(α0 ), c(α1 ) + wℓ(α) }.

(7)

Indeed, c(⊤) must be 0 obviously. When c(α0 ) equals the maximum weight in all
the combinations which leaves the item ℓ(α), and c(α1 ) is the opposite, c(α) must
be the maximum of c(α0 ) and c(α1 ) + wℓ(α) .

4.2

Relation Based on Upper BoundThe second future dominance relation is based on the comparison between an upperbound of a state and a greedy extension of another state.
Let us define a process for generating a greedy extension of a state s as follows:
We start at the node β = s.α. While β ̸= ⊤, we trace 1-arc and update β = β1 .
According to this process, we trace 1-arcs as much as possible, i.e. we try to takeitems while the capacity is enough. Let g(α) be the valued vector obtained by theabove process starting at a node α. It can be represented by the recursion formuladefined by:g(⊤) = 0, g(α) = g(α1 ) + v ℓ(α) .

(8)The valued vector of a greedy extension of a state s is s.v + g(s.α) ∈ E(s).
For a node α, let us define an upper bound on X (α) as follows: a valued vector
u is an upper bound on X (α) iﬀ max{vi (X) | X ∈ X (α)} ≤ ui (i = 1, . . . , m).

6

Hirofumi Suzuki and Shin-ichi Minato

Let u(α) be the valued vector which is the tight upper bound on X (α). We cancalculate u(α) by the recursion formula defined by:ℓ(α)u(⊤) = 0, ui (α) = max{ui (α0 ), ui (α1 ) + vi

} (i = 1, . . . , m).

(9)Indeed, 0 is the tight upper bound on X (⊤) = ϕ obviously. When u(αb ) is thetight upper bound on X (αb ) (b ∈ {0, 1}), ui (α) should be the maximum of ui (α0 )ℓ(α)
and ui (α1 ) + vi
for each i = 1, . . . , m. The valued vector of an upper boundcalculated from a state s is s.v + u(s.α).
Using greedy extensions and upper bounds, we can construct a future dominancerelation as follows: For two states s, s′ ∈ Si (i = 1, . . . , n), if s.v + u(s.α) <s′ .v + g(s′ .α), then e < s′ .v + g(s′ .α) for all e ∈ E(s), because ei ≤ s.vi + ui (s.α)
for each i = 1, . . . , m. This situation matches the condition (4). Thus we define
the future dominance relation ∆u on Si (i = 1, . . . , n) by:∀s, s′ ∈ Si , si ∆u s′i ⇐⇒ s.v + u(s.α) < s′ .v + g(s′ .α).

5Algorithm

5.1

Preprocess(10)

For evaluating the future dominance relations ∆c and ∆u , we can calculate c(α),g(α), and u(α) for all nodes α ∈ N beforehand. We conduct the bottom-up DP
with recursion formula (7), (8), and (9). Initially, we set c(⊤) ← 0, g(⊤) ← 0, andu(⊤) ← 0. After that we process the nodes in reverse topological order (i.e. ⊤ toρ). The pseudo code of preprocess is represented in Algorithm 1.
Algorithm 1 Preprocess for calculating c(α), g(α), and u(α)
1: c(⊤) ← 0, g(⊤) ← 0, u(⊤) ← 0
2: for α ∈ N in the reverse topological order do
3:j ← ℓ(α)4:c(α) ← max{c(α0 ), c(α1 ) + wj }5:g(α) ← g(α1 ) + v j
6:ui (α) ← max{ui (α0 ), ui (α1 ) + vij } for i = 1, . . . , m
7: end for

5.2

Generating ZDD for P

For generating a ZDD for P, we should store the copy of all the states and thetransitions in the DP. We start at a ZDD with only a root node. After that, every
time a transition from a state is occured in the DP, we create a new arc and a
new child node which corresponds to the transition. We show the details of thisprocess in the following.

ZDD-Based Enumeration of Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack ...

7

Let N ′ be a set of new generated nodes, and A′ be a set of new generated arcs.
Let N ′ (s) be a node which corresponds to a state s. For the initial state sϕ , wecreate a root node ρ′ and set N ′ (sϕ ) ← ρ′ . When we create a state sb (b ∈ {0, 1})
by the transition from a state s, if sb is not already created in the DP, we also
create a new node β where ℓ(β) = ℓ(sb .α), and set N ′ (sb ) ← β. At that time, βbecomes a b-child of N ′ (s). Then we create a b-arc which points N ′ (s) to β, andadd it to A′ .
In the pruning phase, if a state s is pruned, we update N ′ (s) ← ⊥. As a
special case, when we conduct a transition from a state s where s.α0 = s.α1 ,we generate only s1 and prune s0 immediately, because c(s0 .α) = c(s1 .α) ands0 .v < s1 .v = s0 .v + v ℓ(s.α) (i.e. s0 ∆c s1 ). At the end of the phase n we update
N ′ (s) = ⊤ for all s ∈ Sn . This process can store all the states and the transitionof the DP as a ZDD form. Then we get a ZDD Z ′ = (N ′ , A′ ) where X (ρ′ ) = P.
However, Z ′ is not irreducible in allmost all cases, thus we should reduce it.
The pseudo code of the above process is represented in Algorithm 2. For thepruning phase, we design the function pruneDominatedStates in the following.
Algorithm 2 Enumeration of all the pareto-optimal solutions
1: Create ZDD Z = (N , A) for X with a root node ρ, and use Algorithm 1
2: Set N ′ ← ϕ and A′ ← ϕ
3: sϕ .v ← 0, sϕ .α ← ρ, S0 ← {sϕ }, N ′ (sϕ ) ← ρ′
4: for i = 1, . . . , n do
5:for s ∈ Si−1 do6:for b ∈ {0, 1} do
7:
if b = 0 and s.α0 = s.α1 then8:β ← N ′ (s), βb ← ⊥
9:
else
10:
Create sb , and set sb .v ← s.v + b × v i , sb .α ← s.αb11:j ← ℓ(sb .α) − 1
12:
if sb ∈ Sj then13:
Create a b-arc which ponits N ′ (s) to N ′ (sb ) and add it to A′
14:
else
15:
Create a new node β where ℓ(β) = ℓ(sb .α)
16:
N ′ (sb ) ← β, Sj ← Sj ∪ {sb }17:Create a b-arc which points N ′ (s) to β, and add it to A′
18:
end if19:
end if
20:
end for21:
end for22:
pruneDominatedStates(Si , N ′ )23: end for
24: N ′ (s) ← ⊤ for all s ∈ Sn
25: Create Z ′ = (N ′ , A′ ) and apply the reduction rules to Z ′26: return Z ′

8

5.3

Hirofumi Suzuki and Shin-ichi Minato

Pruning Dominated States

Here we discuss about how to apply the future dominance relations ∆c and ∆u . It
is important that we make the pruning process faster as much as possible. Indeed,pruning is the process to take computation time most. For a simple way, we willcompare all pairs of states in O(m|Si |2 ) time at each phase i = 1, . . . , n. We present
some techniques for accelerating the simple process in the following.
Let ≥lex be the reverse lexicographical relation defined on valued vectors as
follows (suppose that a and b are a m-dimensional valued vector respectively):{∃i ∈ {1, . . . , m}, aj = bj (j < i) and ai > bi , ora ≥lex b ⇐⇒(11)∀i ∈ {1, . . . , m}, ai = bi .
Let ≥c be the order relation defined on Si (i = 1, . . . , n) by:{c(s.α) > c(s′ .α), or∀s, s′ ∈ Si , s ≥c s′ ⇐⇒c(s.α) = c(s′ .α) and s.v ≥lex s′ .v.

(12)

If s ≥c s′ , then s is not dominated by s′ on ∆c , because c(s.α) > c(s′ .α) or
s′ .v < s.v is satisfied (note that s.v ≥lex s′ .v ⇒ s′ .v < s.v). Thus, at the pruning
phase for Si , we sort all the states in Si by the decreasing order on ≥c . After that
we examine whether s ∈ Si is dominated on ∆c or not in the sorted order. At thattime, we focus on dominant valued vectors as follows.
Let D be the list of dominant valued vectors with respect to s.v where s ∈ Si .
Initially, we set D = ϕ. After that we update D, and perform a pruning by ∆c asfollows: For each state s ∈ Si , we compare s.v and each valued vector d ∈ D. If
s.v < d, then s is dominated by another state whose valued vector is d, and wedelete s from Si . Otherwise, when d ̸= s.v, we add s.v to D and delete d ∈ D
where d < s.v. This process is performed in O(m|D|) time. Note that |D| ≤ |Si |.
Moreover, to finish the comparison as soon as possible, we sort the list D by
the decreasing order on ≥lex . We suppose that D = {d1 , . . . , d|D| }, and dj ≥lex dk(j < k) in the following. We compare s.v and dj in order of j = 1, . . . , |D|. Whens.v ≥lex dj , we can stop the comparison, because dj is the last element withpossibility to dominate s. After that, when dj ̸= s.v, we insert s.v to the j-th
position of D, and delete dk (j ≤ k) where dk < s.v. Note that D is still sortedby the decreasing order on ≥lex after the insertion and the deletion.
The algorithm to apply ∆c is represented in the first 6 lines of Algorithm 3.
The function updateDominator represented in Algorithm 4 is used to update D
and examine whether a state is dominated or not.
For applying ∆u , we can use the similar techniques of applying ∆c . Let G be thelist of valued vectors with respect to s.v + g(s.α) where s ∈ Si . We can generate G
by applying updateDominator(G, s.v + g(s.α)) for all s ∈ Si . Then G is sorted by
the decreasing order on ≥lex and have no unnecessary valued vector. We suppose

ZDD-Based Enumeration of Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack ...

9that G = {g 1 , . . . , g |G| }, and g j ≥lex g k (j < k) in the following. Then we performa pruning by ∆u as follows: For a state s ∈ Si , let u = s.v +u(s.α). We compare u
and g j in order of j = 1, . . . , |G|. If u ≥lex g j , we stop the comparison. Otherwise,
when u < g j , we delete s from Si . The algorithm to apply ∆u is represented in
the remaining lines of Algorithm 3.
Especially, at n-th pruning phase, Sn corresponds to P after applying ∆c according to the property (5). Thus we do not apply ∆u at n-th pruning phase.
Algorithm 3 pruneDominatedStates(Si , N ′ )1: Create the empty list D
2: for s ∈ Si in the decreasing order on ≥c do
3:
if updateDominator(D, s.v) = ”dominated” then4:
N ′ (s) = ⊥, Si ← Si \ {s}5:
end if
6: end for
7: if i = n then8:
return9: end if
10: Create the empty list G
11: updateDominator(G, s.v + g(s.α)) for all s ∈ Si
12: for s ∈ Si do13:
j ← 1 /* G = {g 1 , . . . , g |G| } where g j ≥lex g k (j < k) */14:
while j ≤ |G| and g j ≥lex s.v + u(s.α) do
15:
if s.v + u(s.α) < g j then16:
N ′ (s) = ⊥, Si ← Si \ {s}
17:
break
18:
end if19:
j ←j+120:
end while
21: end for

5.4

Reordering Heuristics

The order of items is an important issue for single-objective knapsack problems.
It is well-known that the decreasing order with respect to v1i /wi , i.e. value perunit weight, is better to obtain a good solution. For the multi-objective version,
Bazgan et al. proposed the order Omax , which refers to the ranking of items withrespect to each objective. For the details, please refer to [1].
Here we propose a new order which is a natural expansion of single-objective
i /w } forcases as follows: Let pi be the potential vector defined by {v1i /wi , . . . , vmieach i ∈ I. We define the Opot as the decreasing order of the potential vectors onf≥lex . Moreover, we define the Opotas the reverse order of Opot .

10

Hirofumi Suzuki and Shin-ichi Minato

Algorithm 4 updateDominator(DOM , v)
1: j ← 1 /* DOM = {d1 , . . . , d|DOM | } where dj ≥lex dk (j < k) */2: while j <= |DOM | and dj ≥lex v do

if v < dj then4:
return ”dominated”
5:else if v = dj then6:
return ”non dominated”
7:
end if8:
j ←j+19: end while
10: Insert v at the j-th position in DOM
11: Erase dk from DOM where dk < v (j < k)
12: return ”non dominated”
3:

6

Computational experiments and results

All code was implemented in C++ (g++5.4.0 with the -O3 option). We used 64-bit
Ubuntu 16.04 LTS with an Intel Core i7-3930K 3.2 GHz CPU and 64 GB RAM.
All instances satisfy 10 ≤ vji , wi ≤ 100 (i = 1, . . . , n, j = 1, . . . , m) and C = 10n.
The following types of instances were considered.
• Type 1: All values and weights are decided uniformly at random.
∑i• Type 2: All valued vectors satisfy 50m − 10 ≤ m
j=1 vj ≤ 50m + 10 (i =1, . . . , n). This causes negative correlation between the objectives. All weights
are decided uniformly at random.
• Type 3: All values are decided uniformly at random. All weights satisfy
1 ∑m
1 ∑m
i
i
j=1 vj − 10 ≤ wi ≤ m
j=1 vj + 10. This causes positive correlationm
between values and the weights.

6.1

Algorithmic Eﬃciency

We conducted comparison between our algorithm and Bazgan’s algorithm. Bazgan’s algorithm is also based on a DP with pruning. It does not use any supporting
data structures, and does not generate any index of P.
6.1.1

Order of Items

fFirst we compared the three orders presented in section 5.4 (Omax , Opot , and Opot)pot
and random order on 100 instances of each type. Table 1 clearly shows that O
accelerates our algorithm. However, Bazgan’s algorithm have nothing worthy of
special mention. Thus, in the following, we use Opot for reordering of items.

ZDD-Based Enumeration of Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack ...

11

Table 1: Average computation time (sec) on each reordering

Type
1

2

3

6.1.2

n
200
100
70
150
60
50
120
50
35

m
2
3
4
2
3
4
2
3
4

random
5.31
18.42
19.20
7.16
10.81
70.17
18.37
52.91
33.39

Bazgan’s
Omax
Opot
3.05
4.32
19.64
19.17
29.03
21.89
6.15
6.02
16.06
12.94
105.25 70.17
9.24
11.60
40.81
41.47
29.91
29.26

f
Opot

9.79
59.57
81.88
8.42
20.47
126.93
9.89
36.29
26.27

random
10.78
15.98
9.84
11.86
5.84
17.12
35.31
31.30
7.50

Proposal
Omax
Opot
5.81
4.35
11.85
7.59
7.34
5.59
10.37
6.63
7.78
3.69
25.08
9.71
19.55
18.82
23.38 20.95
6.43
5.96

f
Opot
12.96
28.92
30.77
9.99
10.12
40.93
18.22
22.83
6.71

Computation Times

Next we investigated the number of generated states to evaluate an eﬀect of thepruning. According to the table 2, our algorithm generates less states than Bazgan’s algorithm for each case. There are up to 4 times diﬀerences. These results
show that our pruning methods using ZDDs are quite eﬀective. This impact isconnected directly with computation times.
Table 2: Average number of states generated by each algorithm

Type
1
2
3

n
200
150
120

m=2
Bazgan’s Proposal
5632649 2689570
5468682 3052779
7519692 5432447

n
100
60
50

m=3
Bazgan’s Proposal
3101540 1184175
10971703492332035120831832

n
70
50
35

m=4
Bazgan’s Proposal
15315734658971120602282585669268165721

Fig. 2 shows the computation times of our algorithm and Bazgan’s algorithm foreach instance. In many bi-objective instances, the overhead of constructing ZDDs
in our algorithm has appeared greater than the eﬀect of the pruning, because
all the bi-objective cases are relatively easy to be solved. On the other hand, ouralgorithm is clearly faster than Bazgan’s algorithm in the three-objective and fourobjective cases. There are 2 to 5 times diﬀerences in almost all instances. These
results show that our algorithm is eﬃcient for harder problems to be solved.

6.2

Eﬃciency of Indexing

At last we show the number of the pareto-optimal solutions and the size of output ZDDs for each case. Table 3 suggests that pareto-optimal solutions suddenly

12

Hirofumi Suzuki and Shin-ichi Minato

20

Type 1, n = 200

8

10

4
2
6

8

Bazgan's

Bazgan's

100
50

200

50

100

Proposal

150

50
50

100

Proposal

150

20

20

40

60

Proposal

80

ProposalType 3, n = 50

50
00

100

50

200

Type 2, n = 50

100

Proposal

150

200Type 3, n = 35

150
100

400
200
00

10 15 20 25 30 35 40

100

600

200

5

150

20

800

Type 3, n = 120

200

40

00

Bazgan's

Bazgan's

100

15

60

1000

Type 1, n = 70

10

ProposalType 2, n = 60

80

200

150

00

5

100

Type 1, n = 100

150

00

00

10

Bazgan's

4

Proposal

5

40
35
30
25
20
15
10
5
00

Bazgan's

2

200

m=4

Bazgan's

6

00

m=3

Type 2, n = 150

15

Bazgan'sm=2Bazgan's

10

200

400

600

Proposal

5000

800 1000

50100

Proposal

150

200

Figure 2: Computation times (sec) for each instanceincrease as objectives increase. Each pareto-optimal solution has approximately n5
items under the influence of how to generate instances. Thus, the size of the output ZDDs is small enough for the total number of items in all the pareto-optimal
solutions.
Table 3: Average number of pareto-optimal solutions and output ZDD nodes

Type
1
2
3

7

n
200
150
120

m=2
#pareto #nodes
182
1993
310
2485
511
3272

n
100
60
50

m=3
#pareto #node
978
2933
1494
2386
3026
4377

n
70
50
35

m=4
#pareto #node
1674
2904
4201
3607
5227
4319

Conclusion

In this study, we have proposed an algorithm to enumerate pareto-optimal solutions of 0-1 multi-objective knapsack problems. The proposed algorithm is basedon the DP with supporting ZDD, and construct a ZDD indexing all pareto-optimal
solutions. The results showed that the proposed algorithm is faster than a conventional DP in several harder three-objective and four-objective instances. Moreover,the eﬃciency of indexing pareto-optimal solutions is better for the total size of all
the pareto-optimal solutions.

ZDD-Based Enumeration of Pareto-Optimal Solutions for 0-1 Multi-Objective Knapsack ...

13

All the main ideas in this study will be applied to multi-objective combinatorial
optimization problems with linear objective functions. Thus, an important future
work is to construct a generalized method for enumerating pareto-optimal solutions. Also, it is important to make use of ZDDs indexing pareto-optimal solutions
in real world problems.

Acknowledgments
Our work is partly supported by JSPS KAKENHI Scientific Research(S) - Number
15H05711.

References[1] Cristina Bazgan, Hadrien Hugot, and Daniel Vanderpooten. Solving eﬃciently
the 0-1 multi-objective knapsack problem. Computers & OR, 36(1):260–279,
2009.
[2] David Bergman, André A. Ciré, Willem-Jan van Hoeve, and John N. Hooker.
Decision Diagrams for Optimization. Artificial Intelligence: Foundations,
Theory, and Algorithms. Springer, 2016.
[3] V. Chankong and Y. Y. Haimes. Multiobjective decision making. Elsevier
Science Publishing, New York (USA), 1983.
[4] Captivo M. Eugénia, Clı̀maco Jo ao, Figueira José, Martins Ernesto, andSantos José Luis. Solving bicriteria 0-1 knapsack problems using a labelingalgorithm. Comput. Oper. Res., 30(12), October 2003.
[5] Xavier Gandibleux and Arnaud Fréville. Tabu search based procedure forsolving the 0-1 multiobjective knapsack problem: The two objectives case. J.
Heuristics, 6(3):361–383, 2000.
[6] Hans Kellerer, Ulrich Pferschy, and David Pisinger.
Springer, 2004.

Knapsack problems.

[7] Ehrgott Matthias and Gandibleux Xavier. A survey and annotated bibliography of multiobjective combinatorial optimization. OR-Spektrum, 22(4):425–
460, 2000.
[8] Shin-ichi Minato. Zero-suppressed bdds for set manipulation in combinatorial
problems. In DAC, pages 272–277, 1993.
[9] Shin-ichi Minato. Zero-suppressed bdds and their applications. International
Journal on Software Tools for Technology Transfer, 3(2):156–170, 2001.

14

Hirofumi Suzuki and Shin-ichi Minato[10] Meir J. Rosenblatt and Zilla Sinuany-Stern. Generating the discrete eﬃcient
frontier to the capital budgeting problem. Operations Research, 37(3):384–394,
1989.
[11] Junn-Yuan Teng and Gwo-Hshiung Tzeng. A multiobjective programming approach for selecting non-independent transportation investment alternatives.
Transportation Research Part B: Methodological, 30(4):291 – 307, 1996.
[12] Dalessandro Soares Vianna and José Elias Claudio Arroyo. A GRASP algorithm for the multi-objective knapsack problem. In XXIV International
Conference of the Chilean Computer Science Society (SCCC 2004), 11-12
November 2004, Arica, Chile, pages 69–75, 2004.