The first table given below gives the best feasible solution value found by the algorithm given in P.C.Chu and J.E.Beasley "A genetic algorithm for the multidimensional knapsack problem" (1997). Working paper available from the second author at the Management School, Imperial College, London SW7 2AZ. The second table given below gives the value of the LP relaxation for each of the problems. Problem Name Best Feasible Solution Value 5.100-00 24381 5.100-01 24274 5.100-02 23551 5.100-03 23534 5.100-04 23991 5.100-05 24613 5.100-06 25591 5.100-07 23410 5.100-08 24216 5.100-09 24411 5.100-10 42757 5.100-11 42545 5.100-12 41968 5.100-13 45090 5.100-14 42218 5.100-15 42927 5.100-16 42009 5.100-17 45020 5.100-18 43441 5.100-19 44554 5.100-20 59822 5.100-21 62081 5.100-22 59802 5.100-23 60479 5.100-24 61091 5.100-25 58959 5.100-26 61538 5.100-27 61520 5.100-28 59453 5.100-29 59965 5.250-00 59312 5.250-01 61472 5.250-02 62130 5.250-03 59446 5.250-04 58951 5.250-05 60056 5.250-06 60414 5.250-07 61472 5.250-08 61885 5.250-09 58959 5.250-10 109109 5.250-11 109841 5.250-12 108489 5.250-13 109383 5.250-14 110720 5.250-15 110256 5.250-16 109016 5.250-17 109037 5.250-18 109957 5.250-19 107038 5.250-20 149659 5.250-21 155940 5.250-22 149316 5.250-23 152130 5.250-24 150353 5.250-25 150045 5.250-26 148607 5.250-27 149772 5.250-28 155075 5.250-29 154662 5.500-00 120130 5.500-01 117837 5.500-02 121109 5.500-03 120798 5.500-04 122319 5.500-05 122007 5.500-06 119113 5.500-07 120568 5.500-08 121575 5.500-09 120699 5.500-10 218422 5.500-11 221191 5.500-12 217534 5.500-13 223558 5.500-14 218962 5.500-15 220514 5.500-16 219987 5.500-17 218194 5.500-18 216976 5.500-19 219693 5.500-20 295828 5.500-21 308077 5.500-22 299796 5.500-23 306476 5.500-24 300342 5.500-25 302560 5.500-26 301322 5.500-27 306430 5.500-28 302814 5.500-29 299904 10.100-00 23064 10.100-01 22801 10.100-02 22131 10.100-03 22772 10.100-04 22751 10.100-05 22777 10.100-06 21875 10.100-07 22635 10.100-08 22511 10.100-09 22702 10.100-10 41395 10.100-11 42344 10.100-12 42401 10.100-13 45624 10.100-14 41884 10.100-15 42995 10.100-16 43559 10.100-17 42970 10.100-18 42212 10.100-19 41207 10.100-20 57375 10.100-21 58978 10.100-22 58391 10.100-23 61966 10.100-24 60803 10.100-25 61437 10.100-26 56377 10.100-27 59391 10.100-28 60205 10.100-29 60633 10.250-00 59187 10.250-01 58662 10.250-02 58094 10.250-03 61000 10.250-04 58092 10.250-05 58803 10.250-06 58607 10.250-07 58917 10.250-08 59384 10.250-09 59193 10.250-10 110863 10.250-11 108659 10.250-12 108932 10.250-13 110037 10.250-14 108423 10.250-15 110841 10.250-16 106075 10.250-17 106686 10.250-18 109825 10.250-19 106723 10.250-20 151790 10.250-21 148772 10.250-22 151900 10.250-23 151275 10.250-24 151948 10.250-25 152109 10.250-26 153131 10.250-27 153520 10.250-28 149155 10.250-29 149704 10.500-00 117726 10.500-01 119139 10.500-02 119159 10.500-03 118802 10.500-04 116434 10.500-05 119454 10.500-06 119749 10.500-07 118288 10.500-08 117779 10.500-09 119125 10.500-10 217318 10.500-11 219022 10.500-12 217772 10.500-13 216802 10.500-14 213809 10.500-15 215013 10.500-16 217896 10.500-17 219949 10.500-18 214332 10.500-19 220833 10.500-20 304344 10.500-21 302332 10.500-22 302354 10.500-23 300743 10.500-24 304344 10.500-25 301730 10.500-26 304949 10.500-27 296437 10.500-28 301313 10.500-29 307014 30.100-00 21946 30.100-01 21716 30.100-02 20754 30.100-03 21464 30.100-04 21814 30.100-05 22176 30.100-06 21799 30.100-07 21397 30.100-08 22493 30.100-09 20983 30.100-10 40767 30.100-11 41304 30.100-12 41560 30.100-13 41041 30.100-14 40872 30.100-15 41058 30.100-16 41062 30.100-17 42719 30.100-18 42230 30.100-19 41700 30.100-20 57494 30.100-21 60027 30.100-22 58025 30.100-23 60776 30.100-24 58884 30.100-25 60011 30.100-26 58132 30.100-27 59064 30.100-28 58975 30.100-29 60603 30.250-00 56693 30.250-01 58318 30.250-02 56553 30.250-03 56863 30.250-04 56629 30.250-05 57119 30.250-06 56292 30.250-07 56403 30.250-08 57442 30.250-09 56447 30.250-10 107689 30.250-11 108338 30.250-12 106385 30.250-13 106796 30.250-14 107396 30.250-15 107246 30.250-16 106308 30.250-17 103993 30.250-18 106835 30.250-19 105751 30.250-20 150083 30.250-21 149907 30.250-22 152993 30.250-23 153169 30.250-24 150287 30.250-25 148544 30.250-26 147471 30.250-27 152841 30.250-28 149568 30.250-29 149572 30.500-00 115868 30.500-01 114667 30.500-02 116661 30.500-03 115237 30.500-04 116353 30.500-05 115604 30.500-06 113952 30.500-07 114199 30.500-08 115247 30.500-09 116947 30.500-10 217995 30.500-11 214534 30.500-12 215854 30.500-13 217836 30.500-14 215566 30.500-15 215762 30.500-16 215772 30.500-17 216336 30.500-18 217290 30.500-19 214624 30.500-20 301627 30.500-21 299985 30.500-22 304995 30.500-23 301935 30.500-24 304404 30.500-25 296894 30.500-26 303233 30.500-27 306944 30.500-28 303057 30.500-29 300460 Problem Name LP optimal 5.100-00 2.4585902722e+04 5.100-01 2.4538208990e+04 5.100-02 2.3895828928e+04 5.100-03 2.3724138568e+04 5.100-04 2.4223030317e+04 5.100-05 2.4884237046e+04 5.100-06 2.5793401838e+04 5.100-07 2.3657882201e+04 5.100-08 2.4445615445e+04 5.100-09 2.4635691889e+04 5.100-10 4.2939522302e+04 5.100-11 4.2706702095e+04 5.100-12 4.2165187168e+04 5.100-13 4.5347074057e+04 5.100-14 4.2434122537e+04 5.100-15 4.3082231019e+04 5.100-16 4.2190597806e+04 5.100-17 4.5265473430e+04 5.100-18 4.3567491237e+04 5.100-19 4.4796625645e+04 5.100-20 6.0016555161e+04 5.100-21 6.2228221156e+04 5.100-22 5.9963295743e+04 5.100-23 6.0644210021e+04 5.100-24 6.1338959182e+04 5.100-25 5.9161868131e+04 5.100-26 6.1696080880e+04 5.100-27 6.1727455409e+04 5.100-28 5.9618006304e+04 5.100-29 6.0242912600e+04 5.250-00 5.9442470293e+04 5.250-01 6.1629336004e+04 5.250-02 6.2259544637e+04 5.250-03 5.9578227593e+04 5.250-04 5.9078366431e+04 5.250-05 6.0238933739e+04 5.250-06 6.0525766833e+04 5.250-07 6.1638399573e+04 5.250-08 6.2032594706e+04 5.250-09 5.9050473618e+04 5.250-10 1.0922063965e+05 5.250-11 1.0996033985e+05 5.250-12 1.0864875673e+05 5.250-13 1.0951079181e+05 5.250-14 1.1083424358e+05 5.250-15 1.1036683878e+05 5.250-16 1.0915260655e+05 5.250-17 1.0913766252e+05 5.250-18 1.1012306381e+05 5.250-19 1.0716211983e+05 5.250-20 1.4976567313e+05 5.250-21 1.5608426942e+05 5.250-22 1.4943390230e+05 5.250-23 1.5224481358e+05 5.250-24 1.5046952641e+05 5.250-25 1.5013274568e+05 5.250-26 1.4869705841e+05 5.250-27 1.4990663526e+05 5.250-28 1.5520992437e+05 5.250-29 1.5481879430e+05 5.500-00 1.2023491673e+05 5.500-01 1.1795516424e+05 5.500-02 1.2121332587e+05 5.500-03 1.2088852459e+05 5.500-04 1.2242649395e+05 5.500-05 1.2212597055e+05 5.500-06 1.1921875799e+05 5.500-07 1.2064312783e+05 5.500-08 1.2166328076e+05 5.500-09 1.2080067536e+05 5.500-10 2.1850008325e+05 5.500-11 2.2127240550e+05 5.500-12 2.1761579702e+05 5.500-13 2.2365320947e+05 5.500-14 2.1906746667e+05 5.500-15 2.2061696224e+05 5.500-16 2.2007654782e+05 5.500-17 2.1828270591e+05 5.500-18 2.1705990360e+05 5.500-19 2.1981282298e+05 5.500-20 2.9589637697e+05 5.500-21 3.0815759683e+05 5.500-22 2.9987863506e+05 5.500-23 3.0655412944e+05 5.500-24 3.0041255797e+05 5.500-25 3.0266175013e+05 5.500-26 3.0140024536e+05 5.500-27 3.0651727306e+05 5.500-28 3.0289676134e+05 5.500-29 2.9997371776e+05 10.100-00 2.3480639352e+04 10.100-01 2.3220685777e+04 10.100-02 2.2493743573e+04 10.100-03 2.3087472427e+04 10.100-04 2.3073878254e+04 10.100-05 2.3053487344e+04 10.100-06 2.2257792599e+04 10.100-07 2.2964168711e+04 10.100-08 2.2882437796e+04 10.100-09 2.3090584252e+04 10.100-10 4.1712635959e+04 10.100-11 4.2597319604e+04 10.100-12 4.2759318604e+04 10.100-13 4.5959363096e+04 10.100-14 4.2183118254e+04 10.100-15 4.3377962939e+04 10.100-16 4.3927938964e+04 10.100-17 4.3335827084e+04 10.100-18 4.2611601297e+04 10.100-19 4.1542785010e+04 10.100-20 5.7626334328e+04 10.100-21 5.9268561959e+04 10.100-22 5.8654692433e+04 10.100-23 6.2202247435e+04 10.100-24 6.1170237371e+04 10.100-25 6.1688389972e+04 10.100-26 5.6663343754e+04 10.100-27 5.9663685279e+04 10.100-28 6.0518795132e+04 10.100-29 6.0986057160e+04 10.250-00 5.9489339237e+04 10.250-01 5.9024301618e+04 10.250-02 5.8413150128e+04 10.250-03 6.1262996954e+04 10.250-04 5.8363341572e+04 10.250-05 5.9052327288e+04 10.250-06 5.8894666665e+04 10.250-07 5.9204526838e+04 10.250-08 5.9701693112e+04 10.250-09 5.9495159378e+04 10.250-10 1.1114715301e+05 10.250-11 1.0894761747e+05 10.250-12 1.0921136647e+05 10.250-13 1.1030649459e+05 10.250-14 1.0872851736e+05 10.250-15 1.1110679918e+05 10.250-16 1.0637133258e+05 10.250-17 1.0692273460e+05 10.250-18 1.1009444234e+05 10.250-19 1.0697307190e+05 10.250-20 1.5203138663e+05 10.250-21 1.4902161650e+05 10.250-22 1.5214125987e+05 10.250-23 1.5149002143e+05 10.250-24 1.5216955171e+05 10.250-25 1.5232675542e+05 10.250-26 1.5336543619e+05 10.250-27 1.5376516339e+05 10.250-28 1.4937282630e+05 10.250-29 1.4991672245e+05 10.500-00 1.1801947688e+05 10.500-01 1.1943728755e+05 10.500-02 1.1940570001e+05 10.500-03 1.1906609340e+05 10.500-04 1.1669795500e+05 10.500-05 1.1970995427e+05 10.500-06 1.2003331236e+05 10.500-07 1.1854570561e+05 10.500-08 1.1800159642e+05 10.500-09 1.1944064466e+05 10.500-10 2.1755291667e+05 10.500-11 2.1925519173e+05 10.500-12 2.1798778166e+05 10.500-13 2.1704066999e+05 10.500-14 2.1401031384e+05 10.500-15 2.1526133241e+05 10.500-16 2.1810919852e+05 10.500-17 2.2017555900e+05 10.500-18 2.1456104137e+05 10.500-19 2.2108363678e+05 10.500-20 3.0455503161e+05 10.500-21 3.0255296929e+05 10.500-22 3.0258154377e+05 10.500-23 3.0095672281e+05 10.500-24 3.0458473485e+05 10.500-25 3.0195251570e+05 10.500-26 3.0513972652e+05 10.500-27 2.9663657338e+05 10.500-28 3.0154762738e+05 10.500-29 3.0724999467e+05 30.100-00 2.2579069212e+04 30.100-01 2.2367844631e+04 30.100-02 2.1270501365e+04 30.100-03 2.2049634468e+04 30.100-04 2.2531454669e+04 30.100-05 2.2910072356e+04 30.100-06 2.2530091561e+04 30.100-07 2.2088758696e+04 30.100-08 2.3201206906e+04 30.100-09 2.1524818140e+04 30.100-10 4.1276362342e+04 30.100-11 4.1866733659e+04 30.100-12 4.2232960640e+04 30.100-13 4.1634875036e+04 30.100-14 4.1410884850e+04 30.100-15 4.1603163557e+04 30.100-16 4.1616130334e+04 30.100-17 4.3388049309e+04 30.100-18 4.2656562926e+04 30.100-19 4.2262702368e+04 30.100-20 5.7987771072e+04 30.100-21 6.0486824869e+04 30.100-22 5.8541843041e+04 30.100-23 6.1239524289e+04 30.100-24 5.9380820171e+04 30.100-25 6.0452579964e+04 30.100-26 5.8635340471e+04 30.100-27 5.9550708673e+04 30.100-28 5.9520220087e+04 30.100-29 6.1140159137e+04 30.250-00 5.7430148056e+04 30.250-01 5.9080031355e+04 30.250-02 5.7176741169e+04 30.250-03 5.7568920302e+04 30.250-04 5.7277695761e+04 30.250-05 5.7844080772e+04 30.250-06 5.6922694564e+04 30.250-07 5.7106212879e+04 30.250-08 5.8097727984e+04 30.250-09 5.7036642112e+04 30.250-10 1.0825806939e+05 30.250-11 1.0889980003e+05 30.250-12 1.0690571505e+05 30.250-13 1.0739661415e+05 30.250-14 1.0795409221e+05 30.250-15 1.0776320907e+05 30.250-16 1.0685085514e+05 30.250-17 1.0457408643e+05 30.250-18 1.0737384099e+05 30.250-19 1.0632177906e+05 30.250-20 1.5057431759e+05 30.250-21 1.5034149611e+05 30.250-22 1.5343428876e+05 30.250-23 1.5368977130e+05 30.250-24 1.5069772675e+05 30.250-25 1.4899654437e+05 30.250-26 1.4791467495e+05 30.250-27 1.5331233569e+05 30.250-28 1.5003790210e+05 30.250-29 1.5003766186e+05 30.500-00 1.1661900812e+05 30.500-01 1.1537013003e+05 30.500-02 1.1734245146e+05 30.500-03 1.1594640475e+05 30.500-04 1.1707928723e+05 30.500-05 1.1637755190e+05 30.500-06 1.1468965116e+05 30.500-07 1.1484782826e+05 30.500-08 1.1590260715e+05 30.500-09 1.1766877110e+05 30.500-10 2.1860152124e+05 30.500-11 2.1507471096e+05 30.500-12 2.1640106546e+05 30.500-13 2.1835048329e+05 30.500-14 2.1609450996e+05 30.500-15 2.1632735471e+05 30.500-16 2.1637630351e+05 30.500-17 2.1701408904e+05 30.500-18 2.1783918183e+05 30.500-19 2.1521847532e+05 30.500-20 3.0203875769e+05 30.500-21 3.0045499590e+05 30.500-22 3.0550120796e+05 30.500-23 3.0245621345e+05 30.500-24 3.0490135100e+05 30.500-25 2.9740943728e+05 30.500-26 3.0376588127e+05 30.500-27 3.0740249604e+05 30.500-28 3.0360592389e+05 30.500-29 3.0102062978e+05