
The 01 unidimensional knapsack problem with two objectives is defined as follow:
Max sum{i=1,…,n} c1(i) x(i)
Max sum{i=1,…,n} c2(i) x(i)
s/t sum{i=1,…,n} w(i) x(i) <= W
x(i)=0 or 1 for i=1,...,n
Sets
There are currently 3 sets of instances coming from different origins.
Instances from set 1A
Instances from set 1B
Instances from set 2
All of them correspond to biobjective 01 unidimensional
knapsack problems.
Instances from set 1A
Description
There are currently 05 data files.
They correspond to 05 biobjective 01 unidimensional knapsack problems.
The values (cost vectors and item weights) are uniformly generated. The
instances count between 50 and 500 items. The tightess ratio r = W /
sum(i=1,n) wi is in the range [0.11:0.91].
These data files are the test problem sets from
Xavier Gandibleux, Arnaud Freville.
Tabu Search Based Procedure for Solving the 01
MultiObjective Knapsack Problem: the two objectives case.
Journal of Heuristics, 6 (3) 361383, 2000.
Information provided
(when available) for each instance:
 a report about the numerical characteristics
 the set of non dominated points
 the maximum complete set of solutions
Format
The format of all of these data files is:
number of variables (n), number of objectives (p=2), number of constraints (k=1)
the cost of item i for objective 1 c1(i), i=1,...,n
the cost of item i for objective 2 c2(i), i=1,...,n
the weight of item i, i=1,...,n
the rhs (total capacity) of the constraint
Instances from set 1B
Description
There are currently 40 data files.
They correspond to 10 biobjective 01 unidimensional knapsack problems.
All instances have a tightness ratio r = W / sum(i=1,n) wi equal to 0.5.
For each problem, 4 variants (class A, B, C and D) are given:
1B/A: the weights and the costs are uniformly generated ( in
[1:100] )
1B/B: created from 1B/A by replacing the second vector of costs
by the first one in reverse order
1B/C: vector of costs generated with plateaus of values of
length ≤ 0.1x problem size
1B/D: created from 1B/C by replacing the second vector of costs
by the first one in reverse order
These data files are the test problem sets from
 set 1B/A:
M. Visée, J. Teghem, M. Pirlot and E. L. Ulungu
Twophases Method and Branch and Bound Procedures to
solve the Biobjective Knapsack Problem.
Journal of Global Optimization 12: 139–155 (1998).
 set 1B/B, 1B/C and 1B/D:
Fabien Degoutin and Xavier Gandibleux
Un retour d'expérience sur la
résolution de problèmes combinatoires biobjectifs.
5e journée du groupe de travail Programmation
Mathématique MultiObjectif (PM20),
Angers, France, 17 mai 2002. (slides in french
here)
Information provided
(when available) for each instance:
 a report about the numerical characteristics
 the set of non dominated points
 the maximum complete set of solutions
Format
The format of all of these data files is:
number of variables (n), number of objectives (p=2), number of constraints (k=1)
the cost of item i for objective 1 c1(i), i=1,...,n
the cost of item i for objective 2 c2(i), i=1,...,n
the weight of item i, i=1,...,n
the rhs (total capacity) of the constraint
Instances from set 2
Description
There are currently 50 data files.
They correspond to 3 series named UNCOR, WEAK and STRONG of
biobjective 01 unidimensional knapsack problems.
All instances have a tightness ratio r = W / sum(i=1,n) wi equal to 0.5.
1) UNCOR: 20 instances of 50 variables. The costs and the weights are
uniformly generated in the range [1:300] for ten of them, and in the
range [1:1000] for the others.
2) WEAK: 15 correlated instances of size between 50 and 1000. The
weights are uniformly generated in [1:1000]. The second vector of costs
takes its values in range [111:1000]. The first vector of costs is
randomly chosen in [c2100:c2+100]
3) STRONG: 15 correlated instances of
size between 50 and 1000. The weights are uniformly
generated in [1:1000]. The second vector of costs takes its values in
range [1:1000]. The first vector of costs is equal to wj+100
These data files are the test problem sets from
M. E. Captivo, J. Clímaco, J. Figueira, E. Martins
and J. L. Santos.
Solving bicriteria 01 knapsack problems using a labeling
algorithm.
Computers & Operations Research 30 (2003) 1865–1886.
Information provided
(when available) for each instance:
 a report about the numerical characteristics
 the set of non dominated points
 the maximum complete set of solutions
Format
The format of all of these data files is self described in the files
