OR-Library is a collection of test data sets for a variety of OR problems.
A full list of the test data sets available in OR-Library can be found here.
There are 9 data files: mdmkp_ct1,...,mdmkp_ct9.
These data files each contains 90 test problems which are
the test problems from P. Cappanera and M. Trubian "A local
search based heuristic for the demand constrained multidimensional
knapsack problem", INFORMS JOC, 2003, to appear.
In the paper, an extension of the Multidimensional
Knapsack Problem (MKP) is considered in which there are
greater-than-equal inequalities, besides the standard less-than-equal
constraints. Moreover, the objective function coefficients are not
constrained in sign. We call it Multi-Demand Multidimensional
Knapsack Problem, MDMKP for short.
The problem to be solved is:
(MDMKP) max sum{j=1,...,n} c(j) x(j)
s.t. sum{j=1,...,n} a(i,j) x(j) <= b(i) i=1,...,m
sum{j=1,...,n} a(i,j) x(j) >= b(i) i=m+1,...,m+q
x(j) = 0 or 1 j=1,...,n
MDMKP instances are generated modifying properly the MKP instances solved
in P.C. Chu and J.E. Beasley "A genetic algorithm for the
multidimensional knapsack problem", Journal of Heuristics, vol. 4,
1998, pp63-86.
Given a MKP instance with m <= constraints, 6 MDMKP instances
are generated: one for each combination of costs type (either positive
or mixed) and number q of >= constraints (q = 1, q = m/2 and q = m
respectively).
The format of the data file is:
number of test problems (K=15)
then for each test problem k (k=1,...,K) in turn:
number of variables (n), number of <= constraints (m)
for each <= constraint i (i=1,...,m): the coefficients a(i,j) j=1,...,n
for each <= constraint i (i=1,...,m): the right-hand side b(i)
for each >= constraint i (i=m+1,...,m+m): the coefficients a(i,j) j=1,...,n
for each >= constraint i (i=m+1,...,m+m): the right-hand side b(i)
6 cost coefficients vectors c(j) j=1,...,n
(the first 3 ones correspond to the positive cost case
for q=1, q=m/2 and q=m >= constraints respectively;
the last 3 ones correspond to the mixed cost case
for q=1, q=m/2 and q=m >= constraints respectively).
As an example we report how to extract 6 MDMKP instances from the
following compact instance, which is the first one (out of 15)
in the file mdmkp_ct1.txt ( n = 100 and m = 5 )
100 5
42 41 523 ... 946 651 298
509 883 229 ... 805 881 850
806 361 199 ... 331 254 447
404 197 817 ... 993 525 322
475 36 287 ... 261 350 635
11927 13727 11551 13056 13460
556 125 736 ... 223 981 143
413 794 494 ... 945 272 849
907 447 158 ... 738 733 891
547 399 669 ... 630 91 525
599 63 627 ... 107 658 636
13162 13388 12431 12309 10949
835 1102 631 ... 1512 526 1380
980 792 860 ... 774 752 1047
322 797 433 ... 839 591 341
248 494 15 ... 859 -266 646
-86 289 276 ... 227 -21 418
-191 -237 -183 ... 510 -128 -69
From this compact instance the following 6 MDMKP instances can be derived
Instance n = 100, m = 5, q = 1, positive cost case
42 41 523 ... 946 651 298
509 883 229 ... 805 881 850
806 361 199 ... 331 254 447
404 197 817 ... 993 525 322
475 36 287 ... 261 350 635
11927 13727 11551 13056 13460
556 125 736 ... 223 981 143
13162
835 1102 631 ... 1512 526 1380
Instance n = 100, m = 5, q = m/2, positive cost case
42 41 523 ... 946 651 298
509 883 229 ... 805 881 850
806 361 199 ... 331 254 447
404 197 817 ... 993 525 322
475 36 287 ... 261 350 635
11927 13727 11551 13056 13460
556 125 736 ... 223 981 143
413 794 494 ... 945 272 849
13162 13388
980 792 860 ... 774 752 1047
Instance n = 100, m = 5, q = m, positive cost case
42 41 523 ... 946 651 298
509 883 229 ... 805 881 850
806 361 199 ... 331 254 447
404 197 817 ... 993 525 322
475 36 287 ... 261 350 635
11927 13727 11551 13056 13460
556 125 736 ... 223 981 143
413 794 494 ... 945 272 849
907 447 158 ... 738 733 891
547 399 669 ... 630 91 525
599 63 627 ... 107 658 636
13162 13388 12431 12309 10949
322 797 433 ... 839 591 341
Instance n = 100, m = 5, q = 1, mixed cost case
42 41 523 ... 946 651 298
509 883 229 ... 805 881 850
806 361 199 ... 331 254 447
404 197 817 ... 993 525 322
475 36 287 ... 261 350 635
11927 13727 11551 13056 13460
556 125 736 ... 223 981 143
13162
248 494 15 ... 859 -266 646
Instance n = 100, m = 5, q = m/2, mixed cost case
42 41 523 ... 946 651 298
509 883 229 ... 805 881 850
806 361 199 ... 331 254 447
404 197 817 ... 993 525 322
475 36 287 ... 261 350 635
11927 13727 11551 13056 13460
556 125 736 ... 223 981 143
413 794 494 ... 945 272 849
13162 13388
-86 289 276 ... 227 -21 418
Instance n = 100, m = 5, q = m, mixed cost case
42 41 523 ... 946 651 298
509 883 229 ... 805 881 850
806 361 199 ... 331 254 447
404 197 817 ... 993 525 322
475 36 287 ... 261 350 635
11927 13727 11551 13056 13460
556 125 736 ... 223 981 143
413 794 494 ... 945 272 849
907 447 158 ... 738 733 891
547 399 669 ... 630 91 525
599 63 627 ... 107 658 636
13162 13388 12431 12309 10949
-191 -237 -183 ... 510 -128 -69
These files have been contributed by Paola Cappanera and Marco Trubian (email: trubian@dsi.unimi.it)
The largest file is mdmkp_ct9 of size 2000Kb (approximately) The entire set of files are of size 5300Kb (approximately).
Click here to access these files