|
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 bi-objective 01 unidimensional
knapsack problems.
Instances from set 1A
Description
There are currently 05 data files.
They correspond to 05 bi-objective 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 0-1
MultiObjective Knapsack Problem: the two objectives case.
Journal of Heuristics, 6 (3) 361-383, 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 bi-objective 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
Two-phases Method and Branch and Bound Procedures to
solve the Bi-objective 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 bi-objectifs.
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
bi-objective 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 [c2-100: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 0-1 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
|
