Biased Random-Key Genetic Algorithms for the Winner Determination Problem in Combinatorial Auctions Carlos Eduardo de Andrade [email protected] Institute of Computing, University of Campinas, Avenida Albert Einstein 1251, Campinas, SP 13083-852 Brazil. Fl´avio Keidi Miyazawa [email protected] Institute of Computing, University of Campinas, Avenida Albert Einstein 1251, Campinas, SP 13083-852 Brazil. Mauricio G. C. Resende [email protected] Network Evolution Research Department, AT&T Labs Research, 200 S. Laurel Avenue, Middletown, NJ 07748 USA. Rodrigo Franco Toso [email protected] Department of Computer Science, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ 08854 USA. Supplementary material A Instance tightness An important aspect of instances for the winner determination problem (WDP) is their tightness. This metric is used by Chu and Beasley (1998) to craft instances of the Multidimensional Knapsack Problem (MDKP), largely used in the literature as the main benchmark for this problem. The tightness of a constraint j is defined as tj = P cj k∈Bˆ wjk , (1) where cj is the availability of resource j and wjk is the amount of resource j requested by k, as defined in Formulation (2) of the main text. Note that for the WDP, the tightness is 1 , ∀j ∈ M, (2) tj = ˆ |{B : j ∈ B, B ∈ B}| by definition, i.e., the tightness is defined as the inverse of the number of bids that request a certain good. Note that a low tj indicates that good j is required by several bids, probably increasing the problem difficulty. In the Chu and Beasley MDKP instances, every constraint of a given problem has the same tightness, which is either 0.25, 0.5, or 0.75. For the WDP instances, tightness varies for each constraint and depends heavily on the type and size of the problems. For the most classes, as the size increases, tightness decreases, notably for the L2, L7, and LG classes. By definition, for some classes tightness is almost constant as, e.g. L3 c 201x by the Massachusetts Institute of Technology Evolutionary Computation x(x): xxx-xxx C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, R.F. Toso and matching. Table 1 shows the average tightness of each constraint for each class and problem size. Note that the hard “path” instances are not shown since the CATS suite does not generate hard instances for “path” distributions. Table 1: Average of instances tightness. Size Class L2 L3 L4 L6 L7 Arbitrary Matching Paths Regions Scheduling Size LG 2 40 80 200 400 1000 1024 2000 4000 0.347 0.333 0.506 0.433 0.543 0.192 0.347 0.562 0.196 0.317 0.341 0.333 0.436 0.381 0.471 0.207 0.333 0.567 0.220 0.249 0.094 0.333 0.507 0.355 0.111 0.132 0.333 0.350 0.133 0.190 0.098 0.333 0.420 0.314 0.109 0.140 0.333 0.375 0.135 0.252 0.019 0.333 0.555 0.351 0.015 0.134 0.333 0.192 0.133 0.202 0.026 0.208 0.605 0.578 0.068 0.138 0.333 — 0.135 0.114 0.012 0.333 0.514 0.351 0.009 0.130 0.333 0.171 0.134 0.195 0.008 0.333 0.511 0.344 0.004 0.131 0.333 0.143 0.131 0.216 1000/500 0.317 1000/1000 0.249 1500/1500 0.190 Evolutionary Computation Volume x, Number x BRKGAs for the WDP in Combinatorial Auctions B Statistical tests Tables 2–9, show U test results for each pair of algorithms and different instance sizes, at 99% of confidence level. The structure of these tables is as follows: Each row and column is indexed by one algorithm. Each element in the diagonal (bold) is the median of the corresponding algorithm. The upper-right diagonal elements are the differences in location statistics for each pair of algorithms. A positive difference indicates that the “row algorithm” has its location statistics higher (better) than the “column algorithm”, and the negative difference is the opposite. The bottom-left diagonal elements are the p-values of each test. We omitted all p < 0.01 values, that indicate that the difference is statistically significant for those pairs. We also omitted confidence intervals since for all tests the values lie in these intervals and they are very narrow. For instance, in Table 2 we can see that the location statistics for CPLEX (2nd line) are higher (better) than for RGRK (4th column) since the value 0.0806 is positive. Since the p-value for this pair was omitted (3rd line, 3rd column), the table indicates that CPLEX performed significantly better than RGRK in these tests. We chose to display a large number of significant digits since for some pairs of algorithms the differences are very small they are still statistically significant. This is the case, for example, of algorithms GARA and SDLP in Table 2 where the difference is only 0.000009 but is still significant (in terms of the U test) in favor of GARA . Since several tests were performed, we applied a p-value correction procedure based on false discovery rate (Benjamini and Hochberg, 1995) aiming to minimize the number of false positives (Type I error). Evolutionary Computation Volume x, Number x 3 CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP 0.000000 −0.950720 0.982822 −0.840038 0.080600 0.875503 −0.916819 0.018096 −0.051401 0.939643 −0.999908 −0.001477 −0.114096 −0.051826 1.000000 −0.999944 −0.003086 −0.115350 −0.053154 −0.000036 1.000000 −0.988866 −0.000017 −0.104717 −0.042700 0.000002 0.000005 1.000000 −0.999941 −0.002008 −0.114523 −0.051845 0.000014 0.000037 −0.000067 1.000000 −0.930584 0.004974 −0.062547 −0.000850 0.034406 0.035707 0.026002 0.034429 0.955629 −0.961331 −0.000078 −0.088295 −0.025455 0.000695 0.003093 0.000012 0.001266 −0.010476 0.951900 p > 0.29 p > 0.07 Table 3: Difference in median location for cost distributions for instances with 400 bids or less, using a confidence interval of 99%. The omitted p-values are less than 0.004. Evolutionary Computation CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP 0.999984 −0.000062 1.000000 −0.000052 0.000083 1.000000 −0.000033 0.000000 −0.000049 1.000000 −0.000012 0.000000 −0.000057 −0.000039 1.000000 −0.000042 0.000000 −0.000029 −0.000011 −0.000047 1.000000 −0.000031 0.000000 −0.000070 −0.000041 0.000012 0.000071 1.000000 −0.000037 0.000000 −0.000077 −0.000016 −0.000077 0.000022 −0.000037 1.000000 −0.000017 0.000000 −0.000007 −0.000046 0.000063 0.000060 0.000041 0.000083 1.000000 −0.000039 0.000000 −0.000026 −0.000025 −0.000068 −0.000089 −0.000007 −0.000032 −0.000076 0.999300 p > 0.09 p > 0.25 p > 0.08 p > 0.86 p > 0.01 p > 0.30 C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, R.F. Toso 4 Table 2: Difference in median location for cost distributions for all instances, using a confidence interval of 99%. The omitted p-values are less than 0.0009. Volume x, Number x Evolutionary Computation Table 4: Difference in median location for cost distributions for instances with 1000 bids or more, using a confidence interval of 99%. The omitted p-values are less than 0.001. Volume x, Number x CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP 0.000000 −0.946779 0.953821 −0.856397 0.079737 0.863907 −0.922194 0.022089 −0.056439 0.926657 −0.999946 −0.035372 −0.124063 −0.062474 1.000000 −0.999927 −0.035907 −0.124426 −0.062700 −0.000065 1.000000 −0.990230 −0.023595 −0.112816 −0.053631 0.000065 0.000086 0.993222 −0.999915 −0.034921 −0.123114 −0.061591 0.000018 0.000071 −0.000044 1.000000 −0.931543 0.014744 −0.062318 −0.005172 0.051891 0.052948 0.043039 0.051161 0.938537 −0.957204 −0.000004 −0.088282 −0.029241 0.027844 0.028406 0.017885 0.027183 −0.021078 0.951700 p > 0.27 p > 0.03 Table 5: Difference in median location for cost distributions for LG 1500/1500 instances, using a confidence interval of 99%. The omitted p-values are less than 0.00001. RGRK BOMA CARA CALP GARA GALP SDRA SDLP 0.827570 −0.081040 0.910548 −0.163875 −0.083920 1.000000 p > 0.05 −0.162074 −0.083313 0.000027 1.000000 −0.154572 −0.076227 0.000036 0.000036 0.998888 −0.160352 −0.079144 0.000045 0.000057 −0.000042 1.000000 −0.102957 −0.022304 0.057928 0.057150 0.050617 0.054981 0.935822 p > 0.01 −0.109679 −0.028658 0.053322 0.052600 0.042824 0.047942 −0.005051 0.942900 p > 0.01 Table 6: Difference in median location of cost distributions for all instances, considering the best solutions until 100 generations. A confidence interval of 99% was used. The omitted p-values are less than 0.000009. 5 RGRK BOMA CARA CALP GARA GALP SDRA SDLP RGRK BOMA CARA CALP GARA GALP SDRA SDLP 0.365256 −0.027354 0.410741 −0.484062 −0.433579 0.971370 −0.495047 −0.443894 −0.000033 0.995975 −0.439106 −0.389594 0.000045 0.000040 0.894743 −0.495536 −0.444571 −0.000016 0.000046 −0.000053 0.993376 −0.082448 −0.028155 0.313978 0.321063 0.274147 0.321429 0.541106 −0.251942 −0.208201 0.115553 0.124509 0.069280 0.126418 −0.126061 0.721500 p > 0.84 BRKGAs for the WDP in Combinatorial Auctions RGRK BOMA CARA CALP GARA GALP SDRA SDLP RGRK BOMA CARA CALP GARA GALP SDRA SDLP RGRK BOMA CARA CALP GARA GALP SDRA SDLP 0.713545 −0.000017 1.000000 −0.000011 0.000005 0.990978 p > 0.01 p > 0.37 p > 0.04 p > 0.37 −0.000029 0.000051 −0.000027 0.999988 p > 0.11 p > 0.70 −0.000019 0.000030 0.000008 0.000003 0.999943 p > 0.27 p > 0.09 p > 0.03 −0.000020 0.000067 −0.000006 0.000033 −0.000037 0.999986 p > 0.01 p > 0.37 −0.000009 0.000038 −0.000000 0.000021 0.000018 0.000039 0.793841 −0.000034 0.000059 −0.000015 −0.000044 −0.000040 −0.000049 −0.000020 1.000000 p > 0.01 p > 0.41 p > 0.52 Table 8: Difference in median location of cost distributions for instances with more than 400 bids, considering the best solutions until 100 generations. A confidence interval of 99% was used. The omitted p-values are less than 0.0001. Evolutionary Computation RGRK BOMA CARA CALP GARA GALP SDRA SDLP RGRK BOMA CARA CALP GARA GALP SDRA SDLP 0.342195 −0.020136 0.370348 −0.548485 −0.521230 0.968853 −0.557676 −0.531241 −0.000039 0.987577 −0.502515 −0.477689 0.009928 0.021097 0.889071 −0.556347 −0.530029 −0.000032 0.000033 −0.020640 0.988826 −0.132994 −0.115826 0.365621 0.375408 0.324260 0.375060 0.530006 −0.300077 −0.284344 0.198026 0.208959 0.154933 0.208850 −0.153962 0.694700 p > 0.70 Table 9: Difference in median location of cost distributions for for LG 1500/1500 instances, considering the best solutions until 100 generations. A confidence interval of 99% was used. The omitted p-values are less than 0.00004. Volume x, Number x RGRK BOMA CARA CALP GARA GALP SDRA SDLP RGRK BOMA CARA CALP GARA GALP SDRA SDLP 0.228827 −0.064896 0.312164 −0.661234 −0.599983 0.991615 p > 0.97 −0.661403 −0.601567 −0.000039 0.991615 −0.608903 −0.544650 0.009253 0.012762 0.890265 p > 0.68 p > 0.68 −0.665038 −0.604113 −0.000065 −0.000056 −0.018571 0.993368 −0.242486 −0.172053 0.418796 0.419685 0.351878 0.421907 0.479321 −0.306383 −0.239376 0.334902 0.334964 0.290690 0.336256 −0.057048 0.548400 C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, R.F. Toso 6 Table 7: Difference in median location of cost distributions for instances with 400 bids or less, considering the best solutions until 100 generations. A confidence interval of 99% was used. The omitted p-values are less than 0.009. BRKGAs for the WDP in Combinatorial Auctions C Additional running time results Table 10 shows the average time in seconds taken by each algorithm to find the best solution (recall that we limited runs to at most 3,600 seconds). The additional time in the last iterations without improvement in the best solution found is disregard. We also exclude the time used loading instances and logging. To be fair with the Java implementations, each run began with a warm-up phase so that Java virtual machine could load and optimize all necessary bytecode. The first two columns of this table list, respectively, the instance classes and their corresponding sizes. Each following pair of columns shows the average time and standard deviation for each algorithm, respectively. Evolutionary Computation Volume x, Number x 7 CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP Evolutionary Computation Class Size Time σ Time σ Time σ Time σ CATS 40 80 200 400 1000 1024 2000 4000 1 2 792 923 2883 2803 2903 3012 1 2 1438 1418 1436 1494 1411 1344 1 1 1 1 382 960 1377 1802 1 1 1 1 1075 1568 1708 1799 10 12 18 40 473 460 1463 2527 6 7 15 56 651 591 1151 1540 1 1 17 51 736 778 1909 2611 1 1 32 121 936 1130 1324 1361 1 2 14 58 53 54 72 52 0 1 74 161 136 142 181 115 1 1 1 28 30 33 35 28 0 0 0 124 96 114 106 75 2 5 31 47 60 72 66 68 1 38 123 139 134 165 135 133 1 1 1 18 36 30 39 42 0 0 0 96 104 106 114 119 2 2 46 65 75 79 78 54 3 4 132 172 167 181 166 123 1 1 1 20 32 28 29 30 0 0 0 89 112 96 99 87 LG 1000 1500 3606 3624 12 23 3601 3601 1 1 289 425 529 702 75 66 68 58 94 118 196 211 93 113 192 200 94 94 196 187 95 100 197 187 78 92 181 188 71 83 168 179 Time σ Time σ Time σ Time σ Time σ Time σ C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, R.F. Toso 8 Table 10: Running time comparison among the algorithms. For each algorithm, it is shown the average time to find the best solutions. The over time used in the last iterations without improvement is disregard. Time in seconds. Volume x, Number x BRKGAs for the WDP in Combinatorial Auctions D Results for parameter tuning RGRK # Best candidates popsize tournamentsize pertubation 434 18 0.1493 472 16 0.1488 437 16 0.1459 BOMA # Best candidates popsize highqualityindividuas diversifiedindividuals maxlocalsearchiters 1377 12 24 142 516 16 26 238 1178 11 24 115 BRKGAs # Best pe 0.2116 0.2527 0.2297 candidates pm rhoe indpop intervalexchange elitexchange 0.1639 0.7609 3 136 2 0.0679 0.7698 3 127 1 0.0741 0.7976 3 141 1 Evolutionary Computation Volume x, Number x 9 C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, R.F. Toso E Best results for each instance This section presents the results obtained for LG instances. The tables format is the following: the first column and second columns are the instance name and the best revenue obtained for this instance, respectively. The following columns show the percentage of the revenue from the best solution obtained by the algorithm that names the column. A high percentage indicates that the obtained solution is closer to the best. A star (?) indicates that the algorithm found the best solution. Table 11: Best results for CATS instances with less than 400 bids. The names of the instances are composed by the class, number of bids, number of goods, and serial number of the instance. Inst. L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L3 L3 L3 L3 L3 L3 L3 L3 L3 L3 L3 L4 L4 L4 L4 L4 L4 L4 L4 L4 L4 L4 L4 L6 L6 L6 L6 L6 L6 L6 L6 L6 L6 L6 L6 L7 L7 L7 L7 L7 L7 L7 40 10 1 40 10 2 40 10 3 80 10 1 80 10 2 80 10 3 200 50 2 200 50 3 400 50 1 400 50 2 400 50 3 40 10 1 40 10 2 40 10 3 80 10 1 80 10 2 80 10 3 200 50 1 200 50 3 400 50 1 400 50 2 400 50 3 40 10 1 40 10 2 40 10 3 80 10 1 80 10 2 80 10 3 200 50 1 200 50 2 200 50 3 400 50 1 400 50 2 400 50 3 40 10 1 40 10 2 40 10 3 80 10 1 80 10 2 80 10 3 200 50 1 200 50 2 200 50 3 400 50 1 400 50 2 400 50 3 40 10 1 40 10 2 40 10 3 80 10 1 80 10 2 80 10 3 200 50 1 Best CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP 8774.7200 9229.3400 8967.4300 9828.2500 9786.7100 9441.1700 45785.7000 49031.9000 46588.7410 47706.0000 47819.7160 2474.2480 2682.7890 2929.2870 2862.1650 2779.9100 2938.3120 12178.8010 12612.9650 14338.1150 14747.9490 14495.9880 9543.8540 8870.7760 9249.9330 9770.0770 9817.6040 9759.7910 45191.2690 44275.5990 46496.4650 47748.4440 47988.4200 48410.5140 8791.5910 9297.1700 9217.2400 9290.9270 9836.4500 9593.9010 41639.9910 38873.5410 40561.3300 44990.9010 46366.8710 45216.8660 8309.1230 9090.6580 8553.2690 9818.5880 9435.4580 9775.6220 28286.0100 ? ? ? 77.64 ? ? ? 87.41 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 86.61 92.24 93.73 89.23 ? ? ? ? ? ? ? ? 96.86 98.44 ? 99.12 99.45 96.18 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.07 99.54 ? ? ? 99.69 99.50 ? 99.65 99.56 ? 99.42 99.56 99.40 ? ? ? ? ? 97.69 95.31 99.62 ? ? 97.48 96.83 ? ? ? 99.32 ? 99.81 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.62 99.55 ? ? ? ? ? ? ? ? ? ? ? 95.86 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.92 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 92.15 ? 98.34 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.53 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Continue in next page. . . 10 Evolutionary Computation Volume x, Number x BRKGAs for the WDP in Combinatorial Auctions Table 11: (continued). Inst. L7 200 50 2 L7 200 50 3 L7 400 50 1 L7 400 50 2 L7 400 50 3 arbitrary 40 10 1 arbitrary 40 10 2 arbitrary 40 10 3 arbitrary 80 10 1 arbitrary 80 10 2 arbitrary 80 10 3 arbitrary 200 50 1 arbitrary 200 50 2 arbitrary 200 50 3 arbitrary 400 50 1 arbitrary 400 50 2 arbitrary 400 50 3 matching 40 10 1 matching 40 10 2 matching 40 10 3 matching 80 10 1 matching 80 10 2 matching 80 10 3 matching 200 50 1 matching 200 50 2 matching 200 50 3 matching 400 50 1 matching 400 50 2 matching 400 50 3 paths 40 10 1 paths 40 10 2 paths 40 10 3 paths 80 10 1 paths 80 10 2 paths 80 10 3 paths 200 50 1 paths 200 50 2 paths 200 50 3 paths 400 50 1 paths 400 50 2 paths 400 50 3 regions 40 10 1 regions 40 10 2 regions 40 10 3 regions 80 10 1 regions 80 10 2 regions 80 10 3 regions 200 50 1 regions 200 50 2 regions 200 50 3 regions 400 50 1 regions 400 50 2 regions 400 50 3 scheduling 40 10 1 scheduling 40 10 2 scheduling 40 10 3 scheduling 80 10 1 scheduling 80 10 2 scheduling 80 10 3 scheduling 200 50 1 scheduling 200 50 2 scheduling 200 50 3 scheduling 400 50 1 scheduling 400 50 2 scheduling 400 50 3 Best CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP 30478.8250 29014.3000 32505.1200 33512.5500 29829.2200 1019.7600 749.5520 679.8568 1038.7469 775.6040 581.9593 3007.5090 3260.1100 3271.8422 4038.0004 3791.8860 4289.3898 10.7792 7.1517 15.6388 13.7825 1.5328 8.1853 32.2974 32.0509 23.8792 41.8873 55.8732 27.1398 4.5826 6.1875 5.3516 7.0575 5.0659 6.0272 20.2063 20.0969 22.1016 26.8886 22.9762 23.7947 942.2510 750.5340 659.7730 808.6960 957.2460 1159.6219 3616.3098 3292.0154 3401.2610 4177.5069 3606.1991 3482.6069 14.7840 15.1235 21.7354 22.6557 15.7918 22.8672 22.6139 53.8402 48.8045 58.2749 70.3185 43.8167 69.46 ? ? ? ? ? 99.98 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 97.32 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1.50 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 96.52 98.74 ? ? ? ? ? ? 96.00 97.54 96.60 93.09 93.80 88.70 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 96.58 ? 98.13 97.69 87.48 92.77 89.33 91.53 93.81 ? ? ? ? ? ? ? ? 95.26 97.38 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 90.48 85.02 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.54 ? 99.72 ? ? ? ? ? 98.13 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 98.15 ? ? ? ? ? ? ? ? 99.13 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Evolutionary Computation Volume x, Number x 11 C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, R.F. Toso Table 12: Best results for CATS instances more than 400 bids. The names of the instances are composed by the class, number of bids, number of goods, and serial number of the instance. Instances with hard in the name have 1024 bids and 256 goods. Inst. L2 1000 256 1 L2 1000 256 2 L2 1000 256 3 L2 2000 512 1 L2 2000 512 2 L2 2000 512 3 L2 4000 1024 1 L2 4000 1024 2 L2 4000 1024 3 L2 hard 1 L2 hard 2 L2 hard 3 L3 1000 256 1 L3 1000 256 2 L3 1000 256 3 L3 2000 512 1 L3 2000 512 2 L3 2000 512 3 L3 4000 1024 1 L3 4000 1024 2 L3 4000 1024 3 L3 hard 1 L3 hard 2 L3 hard 3 L4 1000 256 1 L4 1000 256 2 L4 1000 256 3 L4 2000 512 1 L4 2000 512 2 L4 2000 512 3 L4 4000 1024 1 L4 4000 1024 2 L4 4000 1024 3 L4 hard 1 L4 hard 2 L4 hard 3 L6 1000 256 1 L6 1000 256 2 L6 1000 256 3 L6 2000 512 1 L6 2000 512 2 L6 2000 512 3 L6 4000 1024 1 L6 4000 1024 2 L6 4000 1024 3 L6 hard 1 L6 hard 2 L6 hard 3 L7 1000 256 1 L7 1000 256 2 L7 1000 256 3 L7 2000 512 1 L7 2000 512 2 L7 2000 512 3 L7 4000 1024 1 L7 4000 1024 2 L7 4000 1024 3 L7 hard 1 L7 hard 2 L7 hard 3 arbitrary 1000 256 arbitrary 1000 256 arbitrary 1000 256 arbitrary 2000 512 arbitrary 2000 512 Best 1 2 3 1 2 CORAL CPLEX 244098.0000 ? ? 241158.0000 ? ? 254988.0000 ? ? 495448.0000 ? ? 501810.0000 4.27 ? 505625.0000 ? ? 1000590.0000 ? ? 1010991.6920 10.66 ? 996744.0000 ? ? 262.5110 ? ? 456.5370 ? ? 317.4120 ? ? 64626.2530 75.64 ? 66106.1710 79.20 ? 64987.7430 75.45 ? 128004.7893 81.84 ? 132229.2010 93.59 ? 133133.1410 82.48 ? 263970.8210 78.25 ? 263936.8590 75.72 ? 263404.1096 80.03 ? 75.4074 75.32 ? 34.1897 80.59 99.33 20.8636 82.47 96.79 228752.1550 4.41 ? 229601.7270 92.34 ? 229349.1950 2.85 ? 461218.2640 3.56 ? 459425.3230 2.75 ? 458536.7260 2.64 ? 914322.9910 2.30 ? 920786.4330 2.22 ? 920294.1540 3.27 ? 290.2399 16.81 ? 383.8526 13.76 ? 282.6879 7.06 ? 199757.0790 45.81 ? 200559.8373 69.95 ? 201208.1706 3.72 ? 405788.3937 72.95 ? 411091.1370 5.22 ? 402472.3077 71.43 ? 785686.0929 0.88 ? 801026.0135 75.21 ? 791849.8150 73.60 ? 377.5873 13.69 ? 330.2240 18.25 ? 446.4472 6.50 ? 68830.4000 95.17 ? 79025.8000 96.74 ? 81981.6000 100.00 ? 121043.0000 ? ? 119058.0000 ? ? 122346.0000 99.99 ? 244374.0000 ? ? 229826.0000 ? ? 228342.0000 ? ? 233.0348 73.22 ? 127.4510 100.00 ? 261.2782 83.15 97.72 17186.3016 70.40 96.39 15782.8217 6.06 98.02 17280.1375 9.31 98.04 32267.8600 0.17 96.98 32159.7621 1.56 95.83 RGRK BOMA ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 100.00 ? ? ? ? ? ? ? ? 99.26 99.60 99.08 99.31 99.68 ? 98.80 97.74 99.18 98.78 98.95 98.83 90.99 97.45 91.47 97.29 91.46 96.98 99.35 97.11 96.96 95.45 97.63 96.19 99.52 99.17 99.27 98.48 99.58 99.70 99.48 99.04 99.83 98.97 99.50 99.07 98.33 96.11 98.39 95.88 98.37 96.36 99.53 98.80 99.36 99.14 99.55 98.90 97.22 99.41 97.41 96.57 99.56 99.15 98.00 95.24 97.83 94.81 98.29 95.41 98.15 93.36 98.90 92.95 98.19 93.02 99.57 99.51 99.58 99.65 99.62 99.68 ? ? ? 100.00 ? 100.00 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 97.70 ? 93.12 95.91 96.27 95.63 92.55 97.45 96.15 93.59 96.42 94.28 CARA ? ? ? ? ? ? ? ? ? ? ? ? 99.60 99.75 99.84 99.47 99.49 99.07 99.88 99.48 99.09 99.28 99.27 98.44 99.85 99.71 99.90 99.71 99.73 99.65 99.32 99.09 99.16 ? ? ? 98.23 98.80 98.72 97.76 97.77 97.04 97.30 97.91 97.06 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.18 ? 98.41 98.69 99.74 99.97 CALP ? ? ? ? ? ? ? ? ? ? ? ? 99.60 99.78 ? 99.92 99.71 99.64 99.74 99.62 99.30 99.39 ? 98.63 ? ? ? ? ? ? ? ? 99.99 ? ? ? 98.75 99.39 99.96 99.00 98.16 97.93 97.62 97.66 97.03 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 98.89 ? GARA ? ? ? ? ? ? ? ? ? ? ? ? 99.60 99.78 99.81 99.92 99.35 99.43 98.87 99.60 99.17 99.18 99.09 98.44 ? ? ? ? ? ? ? ? 99.99 ? ? ? 98.32 97.61 98.36 97.85 97.22 97.73 97.54 97.33 96.92 ? ? ? ? ? ? ? ? ? ? ? ? 98.25 ? 99.18 96.87 98.56 99.28 ? 99.39 GALP SDRA SDLP ? ? ? ? ? ? ? ? ? ? ? ? 99.56 99.66 ? 99.72 99.78 99.62 99.50 99.55 98.94 99.35 97.74 ? ? ? ? ? ? ? ? ? 99.99 ? ? ? 98.72 99.39 98.92 99.00 98.16 97.93 97.73 97.84 97.38 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.40 99.28 99.56 99.19 88.40 90.88 81.73 72.84 80.74 87.47 37.53 59.42 34.50 63.91 ? 66.52 96.60 98.58 99.79 98.43 97.62 97.09 96.46 96.62 96.70 98.89 97.17 95.31 99.67 99.43 99.43 99.07 99.32 99.50 99.15 98.93 99.00 ? ? ? 98.22 97.38 97.16 94.39 96.02 94.55 97.60 95.53 95.83 ? ? ? 86.30 96.74 ? 97.56 93.95 92.35 90.59 99.68 88.19 ? ? 95.56 94.46 96.39 97.28 95.35 98.02 ? ? ? ? ? ? ? ? ? ? ? ? 99.50 99.78 ? 99.95 99.69 99.62 99.25 99.53 98.93 99.18 97.74 ? ? ? ? ? ? ? ? ? 99.99 ? ? ? 98.22 99.11 98.36 99.00 97.77 97.93 97.75 95.95 96.82 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 95.56 95.53 98.03 97.28 96.13 97.21 Continue in next page. . . 12 Evolutionary Computation Volume x, Number x BRKGAs for the WDP in Combinatorial Auctions Table 12: (continued). Inst. Best arbitrary 2000 512 3 arbitrary 4000 1024 1 arbitrary 4000 1024 2 arbitrary 4000 1024 3 arbitrary hard 1 arbitrary hard 2 arbitrary hard 3 matching 1000 256 1 matching 1000 256 2 matching 1000 256 3 matching 2000 512 1 matching 2000 512 2 matching 2000 512 3 matching 4000 1024 1 matching 4000 1024 2 matching 4000 1024 3 matching hard 1 matching hard 2 matching hard 3 paths 1000 256 1 paths 1000 256 2 paths 1000 256 3 paths 2000 512 1 paths 2000 512 2 paths 2000 512 3 paths 4000 1024 1 paths 4000 1024 2 paths 4000 1024 3 regions 1000 256 1 regions 1000 256 2 regions 1000 256 3 regions 2000 512 1 regions 2000 512 2 regions 2000 512 3 regions 4000 1024 1 regions 4000 1024 2 regions 4000 1024 3 regions hard 1 regions hard 2 regions hard 3 scheduling 1000 256 1 scheduling 1000 256 2 scheduling 1000 256 3 scheduling 2000 512 1 scheduling 2000 512 2 scheduling 2000 512 3 scheduling 4000 1024 1 scheduling 4000 1024 2 scheduling 4000 1024 3 scheduling hard 1 scheduling hard 2 scheduling hard 3 CORAL 32181.8011 2.52 62694.3745 1.43 61809.4598 0.35 62366.9031 79.65 16412.4678 1.32 15699.7262 71.07 14954.8919 1.29 724.3030 26.06 731.8279 94.91 912.8670 92.44 669.1193 30.47 1379.1604 92.92 881.3102 24.14 3047.5592 64.56 2302.0147 38.07 2508.6253 31.33 155.0591 ? 421.5402 23.49 323.9873 94.06 57.7328 89.93 65.7292 28.17 57.4862 30.51 90.3558 62.85 101.4873 52.98 106.9681 57.30 161.5959 99.87 165.5882 80.80 150.9125 97.21 16214.3571 74.32 17922.5058 75.94 17391.3627 3.78 38262.6408 74.08 32274.1576 62.09 37199.7468 1.20 65807.6502 0.33 65628.9304 2.72 64800.3099 5.43 15336.4868 72.73 17988.3370 70.19 16777.2344 72.67 44.9038 22.99 42.5548 20.98 87.6889 11.41 40.9792 25.74 58.2106 3.63 48.2352 1.32 28.3994 ? 45.9743 ? 36.6752 ? 168.4070 98.37 1219.4075 100.00 4812.6430 56.44 CPLEX RGRK BOMA 95.86 96.79 95.70 93.86 97.64 93.42 96.20 93.46 99.78 94.33 98.47 96.52 99.40 95.34 ? 99.88 ? 99.92 ? ? ? 99.91 ? 99.72 ? 99.93 ? 94.35 ? 94.29 ? 95.11 ? ? ? 99.96 ? ? ? ? ? ? ? ? ? 100.00 ? 99.83 ? 99.80 ? 98.26 ? 98.52 ? 98.70 ? 95.20 ? 95.60 ? 97.09 ? 97.36 ? 95.82 ? 96.77 99.97 94.38 99.70 95.57 ? 95.15 ? 94.01 ? 94.17 ? 93.30 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? CARA CALP GARA GALP SDRA SDLP 97.81 99.54 99.27 ? 99.04 97.77 98.95 91.57 99.64 98.48 98.56 ? 96.90 96.76 90.90 97.84 98.90 ? 97.92 96.32 95.92 90.80 98.82 99.01 97.84 ? 96.39 95.77 95.55 ? 99.78 98.07 99.78 95.12 96.07 98.13 ? 98.47 98.02 98.47 98.26 99.65 98.76 99.91 99.43 99.69 99.43 ? ? 99.88 ? ? ? ? ? ? 99.99 ? ? ? ? 99.99 ? 99.97 ? ? ? ? 99.82 ? 99.51 ? ? ? ? 99.84 ? 99.48 ? ? ? ? 99.96 ? 99.35 ? ? ? ? 99.76 ? 98.41 99.98 ? ? ? 99.82 ? 98.19 100.00 ? ? ? 99.78 ? 98.39 99.94 ? ? ? 99.87 ? ? ? ? ? ? ? ? 99.96 ? ? ? ? ? ? 99.99 ? ? ? ? ? ? ? ? ? ? ? ? ? 98.37 ? ? ? ? ? ? ? ? ? ? ? 99.17 ? 95.94 ? ? ? ? ? ? 97.01 ? ? 100.00 99.98 99.21 99.98 97.50 99.92 99.87 99.87 99.87 99.41 99.87 91.88 99.70 ? ? ? 98.50 ? 93.20 99.47 ? ? ? 98.79 ? 91.61 99.82 ? ? ? 98.99 ? 98.99 98.94 99.36 98.12 99.36 98.09 98.89 99.63 99.23 98.67 99.10 98.79 98.87 98.67 ? 99.54 99.54 98.18 99.34 97.85 99.34 97.88 98.30 99.55 98.68 98.99 97.65 98.86 95.49 99.77 98.64 97.89 98.60 96.23 97.45 98.55 99.21 99.59 98.49 99.50 97.50 98.95 96.23 99.56 99.28 97.14 ? 96.09 96.67 97.09 99.91 ? 98.25 99.30 98.75 98.97 95.79 99.06 99.04 96.26 99.42 94.39 95.07 98.24 99.82 99.82 99.22 99.82 98.55 99.82 99.48 99.48 99.74 98.55 99.74 99.74 99.48 98.03 99.17 99.66 98.75 99.66 97.94 98.35 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Table 13: Best results for LG 1000/500 instances. Inst. Best CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP in101 in102 in103 in104 in105 in106 in107 in108 in109 72724.6180 72518.2220 72129.5000 72709.6470 75646.1406 71258.6130 69713.4030 75813.2109 69475.8950 37.66 45.17 40.67 65.30 39.96 51.23 38.64 11.33 38.47 92.27 98.03 96.64 98.04 89.05 89.77 98.38 98.39 91.99 92.27 96.72 95.13 94.46 90.91 93.23 98.38 99.12 95.09 96.03 98.22 96.76 97.42 ? 94.31 99.24 ? 95.34 ? ? ? ? ? ? ? 99.95 ? ? ? ? ? ? ? ? ? ? ? ? 97.41 ? ? ? 99.55 99.12 ? ? ? ? ? ? ? ? 99.95 ? 95.02 97.44 ? 92.45 94.99 94.49 ? 99.31 ? 98.63 99.82 98.43 ? ? ? ? 99.30 ? Continue in next page. . . Evolutionary Computation Volume x, Number x 13 C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, R.F. Toso Table 13: (continued). Inst. Best CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP in110 in111 in112 in113 in114 in115 in116 in117 in118 in119 in120 in121 in122 in123 in124 in125 in126 in127 in128 in129 in130 in131 in132 in133 in134 in135 in136 in137 in138 in139 in140 in141 in142 in143 in144 in145 in146 in147 in148 in149 in150 in151 in152 in153 in154 in155 in156 in157 in158 in159 in160 in161 in162 in163 in164 in165 in166 in167 in168 in169 in170 in171 in172 in173 in174 in175 in176 in177 68295.2890 75133.2900 71342.4830 73365.8906 69224.7656 70221.5610 70032.4609 69982.8330 72160.9870 67038.4297 75514.9300 67639.1250 69546.2730 70618.3130 71686.0469 69233.1220 70671.7700 69273.3203 72179.4310 65751.6490 71075.3000 71177.9062 75510.0469 71253.5610 75781.7490 72138.1172 68903.0938 70072.0469 71989.6330 72840.3940 73665.2310 69605.0770 74777.9850 69699.0547 73197.0730 73695.0150 73746.9375 65878.3020 72116.9690 70800.1800 72839.4240 68834.5010 76224.7812 70110.7650 69215.5240 74936.7730 69704.1300 73934.8438 69489.5430 71091.8047 70606.9180 66266.3710 74720.7940 64976.9910 67950.6230 70361.9531 71460.8930 74523.7656 72097.3210 71827.3400 74564.7490 71279.4840 70361.8070 73677.2030 73523.6094 72924.8740 67761.4830 70187.1540 16.29 42.87 60.02 53.84 13.31 48.33 48.56 59.34 57.56 58.44 58.27 34.44 40.98 49.50 39.54 51.98 9.53 42.94 17.30 37.24 48.78 2.62 43.34 54.48 46.70 2.42 43.37 48.96 28.25 35.02 43.72 40.43 49.90 34.12 49.56 39.38 38.30 58.53 51.94 46.53 46.46 45.83 41.04 43.46 7.16 36.64 50.74 33.75 47.97 55.58 46.45 15.81 54.27 46.23 43.67 39.37 34.20 26.61 43.31 45.18 42.64 37.03 3.68 57.65 44.59 49.45 38.10 49.13 ? 96.74 99.25 92.73 94.35 94.85 98.32 94.96 95.02 96.86 98.85 96.47 96.73 92.25 97.28 95.79 98.45 98.39 94.35 97.51 97.39 95.49 96.88 97.85 96.61 95.49 94.79 ? 97.43 94.24 ? 98.91 97.26 95.14 94.95 96.88 95.29 95.28 96.01 97.27 94.35 99.99 93.71 99.49 94.14 96.51 93.01 91.20 ? 96.38 96.31 92.56 93.32 98.63 93.99 95.13 92.35 ? 97.37 96.43 92.70 96.53 99.57 96.29 96.31 97.54 97.51 94.27 92.75 95.16 94.80 96.02 94.58 93.15 93.80 99.92 93.06 ? 93.41 94.24 98.24 94.96 99.72 95.79 93.05 92.27 90.70 97.51 97.90 99.62 99.90 94.16 91.22 90.72 96.29 90.56 99.24 92.53 92.15 96.15 94.59 98.81 93.48 92.77 93.65 97.17 95.66 95.68 93.20 97.90 93.62 96.81 96.66 96.26 99.24 93.38 92.69 95.46 99.48 93.91 95.58 98.45 91.64 95.97 95.05 96.58 96.68 97.32 92.51 94.32 93.91 93.20 92.89 91.49 95.42 95.49 99.79 97.12 99.81 ? ? 96.06 ? 99.92 97.21 ? 99.95 ? 98.24 99.97 ? 97.41 98.61 ? 98.32 97.59 97.90 ? ? 99.35 98.73 ? ? ? 99.24 98.79 92.42 99.67 96.20 ? 99.03 96.25 ? 97.17 98.84 98.61 98.91 99.13 ? 99.49 98.48 97.22 99.24 ? 97.71 ? 99.48 98.53 97.44 99.06 99.41 ? 97.99 ? 96.86 98.45 95.80 97.33 96.82 99.78 ? 97.26 99.35 98.94 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.24 ? ? ? ? ? ? ? ? ? 99.81 ? ? ? ? ? ? ? ? ? ? ? ? ? 99.44 ? ? ? 99.80 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 98.58 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.27 ? ? ? ? ? ? 99.34 99.44 99.86 ? ? ? ? ? ? ? ? ? ? ? 99.67 ? ? ? ? ? ? 99.56 99.55 ? ? ? 98.36 99.13 ? 99.97 ? ? ? 98.61 ? ? ? 99.14 ? ? 99.35 ? ? 99.86 99.99 99.24 ? ? ? ? ? ? 97.81 ? ? 98.84 99.30 ? ? ? 99.60 99.27 99.75 ? ? ? ? ? ? ? 99.86 ? 98.61 99.45 ? 99.54 98.62 96.46 98.48 99.57 ? ? 99.67 ? ? ? ? ? ? 99.56 ? ? ? ? ? 99.13 ? ? 99.97 ? ? ? ? ? ? ? ? ? ? ? ? 99.86 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.27 ? ? ? ? ? ? ? ? 99.86 ? ? 99.80 ? ? ? ? ? ? ? ? 99.67 ? ? ? 95.53 ? 98.43 96.04 95.95 98.32 95.33 95.36 98.27 97.67 96.34 95.69 98.78 96.63 98.14 95.98 98.74 95.27 97.51 96.04 96.39 ? 94.95 97.39 ? 96.61 ? 99.24 96.13 ? 95.42 97.52 98.19 ? ? 97.29 94.88 99.81 99.02 ? 98.85 97.94 96.54 99.09 99.75 96.64 92.71 ? 98.53 98.61 97.88 99.44 99.06 98.38 97.19 97.56 96.86 ? 95.21 90.03 98.48 97.41 94.10 96.48 99.67 98.33 98.88 ? 97.12 ? ? 96.04 96.95 98.32 98.99 95.36 98.27 98.87 96.34 ? 99.93 99.72 ? 96.62 ? 96.20 97.51 97.90 ? ? 97.67 ? ? 99.04 ? 97.71 98.94 ? 98.91 97.52 98.89 ? 97.80 97.29 94.88 99.81 ? ? 99.75 97.94 98.00 99.27 ? 96.64 ? 95.13 98.53 98.61 ? 99.44 99.06 98.38 97.19 97.83 96.86 ? ? 95.15 98.45 98.66 97.49 95.46 99.67 99.43 98.94 Continue in next page. . . 14 Evolutionary Computation Volume x, Number x BRKGAs for the WDP in Combinatorial Auctions Table 13: (continued). Inst. Best CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP in178 in179 in180 in181 in182 in183 in184 in185 in186 in187 in188 in189 in190 in191 in192 in193 in194 in195 in196 in197 in198 in199 in200 70833.3720 72205.2980 70513.3520 72238.0859 71645.0312 71520.4688 74377.5380 73714.9531 70736.2480 70166.3660 70485.1950 69786.0220 73765.2090 72587.0780 71156.8280 72526.4688 75803.5156 69066.8672 69776.2220 68457.8040 73474.3830 70955.9130 76803.1830 53.70 42.51 54.50 37.33 37.70 37.89 1.74 47.24 47.66 31.20 40.11 38.77 38.54 8.24 34.93 33.95 47.87 29.99 51.81 55.49 41.26 37.03 46.02 90.85 96.80 93.16 95.06 97.82 98.38 92.64 ? 97.98 95.26 93.17 95.35 97.07 99.65 93.02 97.21 94.14 91.41 98.39 ? 98.84 93.84 95.19 92.84 95.57 94.07 97.16 ? 93.86 87.92 94.44 94.98 94.28 95.47 96.84 97.07 97.87 94.22 94.22 ? 96.21 98.47 ? 92.37 95.59 95.17 95.71 96.60 96.53 ? ? ? 94.41 ? 98.72 97.34 96.52 98.82 98.60 98.63 99.45 ? ? ? 99.91 98.33 97.19 99.98 98.09 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 98.97 ? ? ? ? ? 99.52 ? ? 98.86 ? ? 99.65 ? ? ? ? 99.91 ? ? 99.98 98.88 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 94.42 96.60 96.26 96.76 98.80 99.57 ? 99.52 97.98 98.55 99.49 98.54 ? ? 99.61 97.46 99.91 96.25 98.70 97.41 97.19 98.21 ? 95.20 ? 96.31 99.07 98.80 99.57 ? ? 97.98 98.55 ? ? 99.72 ? 99.61 97.46 99.91 96.25 97.77 97.41 97.19 98.34 ? Table 14: Best results for LG 1000/1000 instances. Inst. Best CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP in201 in202 in203 in204 in205 in206 in207 in208 in209 in210 in211 in212 in213 in214 in215 in216 in217 in218 in219 in220 in221 in222 in223 in224 in225 in226 in227 in228 in229 in230 in231 in232 in233 in234 in235 in236 in237 in238 81557.7578 90708.1406 86239.2266 87075.4453 86515.9510 91518.9640 93129.2900 94904.6953 87268.9650 89962.4062 84913.6840 90778.2188 85369.1850 85181.6090 91531.7031 91580.9800 86962.9270 94965.2109 93586.4380 89792.9219 87410.7800 89905.5391 83045.4297 87105.2770 89430.1094 88176.1220 92613.3710 92684.0781 90468.1420 91559.1562 101458.6094 87270.8630 86151.8980 88874.3359 93246.5700 87876.7891 87616.0450 87004.0781 45.28 38.91 7.67 38.39 34.40 19.12 27.22 25.73 47.58 39.71 55.07 40.06 34.71 39.16 46.31 48.61 52.45 45.14 46.99 44.44 41.62 45.82 40.13 49.10 38.68 34.96 44.80 56.28 49.34 48.44 40.11 17.55 39.85 49.60 38.90 38.94 54.09 49.72 94.10 98.60 95.45 94.14 93.59 94.93 ? 88.80 98.88 96.64 93.20 96.81 95.81 97.34 95.42 ? 97.72 90.34 90.94 97.87 ? 94.77 96.04 96.86 95.90 91.75 96.95 96.70 96.50 96.66 93.07 95.18 96.84 98.17 ? 98.10 96.48 98.22 ? 93.30 93.96 94.39 92.44 93.41 97.75 90.18 93.37 95.73 92.87 91.38 97.87 96.19 93.46 93.53 93.77 91.55 96.02 96.82 93.56 90.80 88.95 98.39 91.21 90.75 95.57 96.70 91.38 94.13 88.09 91.66 94.09 92.70 89.98 91.59 94.61 90.70 ? ? ? ? 97.11 94.93 99.99 ? 99.41 ? 99.54 ? 97.87 99.58 ? 94.72 98.33 ? 96.02 ? 97.23 ? ? 99.92 ? 95.92 98.94 ? 96.75 ? ? 99.45 98.81 ? ? ? 98.30 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.12 ? ? ? 99.99 96.71 99.41 ? ? ? ? ? ? ? ? ? ? 98.48 ? ? ? ? ? 95.09 ? ? ? ? ? ? ? ? ? ? ? 99.57 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.71 99.96 97.69 95.49 94.14 ? 94.91 96.71 98.88 98.38 97.60 98.97 98.97 99.58 99.56 ? 97.72 ? 96.08 98.63 96.00 ? 94.30 97.13 ? 95.92 ? 98.86 96.76 97.74 ? 92.66 96.91 96.84 93.01 95.25 97.16 98.70 96.02 ? 97.69 98.62 96.80 ? 94.91 96.71 96.83 ? 98.48 98.97 98.97 ? 97.91 ? 99.92 ? 96.08 98.63 96.23 ? 94.71 97.40 ? 95.92 ? 95.33 96.76 97.74 ? ? 97.09 96.84 97.24 96.84 99.78 ? Continue in next page. . . Evolutionary Computation Volume x, Number x 15 C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, R.F. Toso Table 14: (continued). 16 Inst. Best CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP in239 in240 in241 in242 in243 in244 in245 in246 in247 in248 in249 in250 in251 in252 in253 in254 in255 in256 in257 in258 in259 in260 in261 in262 in263 in264 in265 in266 in267 in268 in269 in270 in271 in272 in273 in274 in275 in276 in277 in278 in279 in280 in281 in282 in283 in284 in285 in286 in287 in288 in289 in290 in291 in292 in293 in294 in295 in296 in297 in298 in299 in300 81435.3020 86608.4120 89961.1641 92480.5420 91839.5970 91029.7940 90590.5630 87158.2344 89044.3828 93058.1406 95169.5190 93775.8359 88734.0770 89504.9220 88253.3125 85897.5010 89368.1990 89253.2656 88605.5950 85183.9110 95397.3516 90407.2050 89790.1900 88470.1100 93087.8530 86498.9141 83621.1700 90038.9920 91438.2109 89482.2790 83546.6830 87509.4062 85951.6810 88642.8220 87909.9070 83417.7890 89915.1500 86626.4375 88537.7270 91326.9531 87058.9800 86529.5938 88470.4141 88985.3290 88915.6590 88241.9750 85953.2490 88323.4844 91652.7400 85639.0090 86032.8140 92103.2070 94188.2910 94063.9650 85810.6210 91167.3160 89267.5156 90000.2970 89725.9360 89166.7422 92218.6094 88373.3281 41.92 45.38 39.00 35.73 37.24 42.40 34.27 24.83 45.42 57.39 62.17 48.37 43.94 53.90 24.40 31.00 37.11 38.86 12.67 44.59 37.58 42.48 46.72 50.02 37.55 48.56 41.51 31.15 24.48 41.41 48.56 34.87 42.83 49.07 39.27 45.77 37.12 50.65 37.49 52.88 46.83 38.92 53.98 46.25 49.94 39.20 45.59 57.41 32.42 41.68 49.01 42.87 59.11 57.29 51.78 49.30 34.74 22.43 27.45 47.96 41.60 48.68 99.86 98.11 98.80 90.80 99.91 95.61 95.38 99.39 96.32 91.53 93.98 ? 92.56 93.49 95.78 96.01 94.69 93.03 96.54 99.33 ? 99.25 ? ? 94.59 97.86 95.48 96.12 99.40 97.93 99.19 97.20 95.87 92.82 99.20 98.89 98.05 99.36 96.56 95.55 ? 97.14 96.51 92.23 95.47 96.30 96.57 92.98 99.46 95.93 96.03 95.79 92.98 97.14 98.18 94.62 94.01 98.55 ? 98.65 98.03 97.91 92.88 98.61 92.63 91.44 91.99 92.89 96.10 ? 96.01 92.92 93.98 ? 92.35 98.03 96.70 96.37 94.32 92.12 94.88 97.74 87.77 92.46 92.80 92.98 94.24 91.86 97.91 94.84 92.66 93.04 96.77 92.81 93.42 95.86 95.06 93.02 94.19 99.40 98.09 96.72 89.91 93.11 95.42 91.56 96.33 96.86 93.35 ? 88.37 96.81 91.94 90.63 95.55 95.96 95.25 91.92 93.08 93.35 94.05 93.52 95.49 ? 99.86 98.61 ? 92.68 99.91 98.11 96.10 ? ? ? 98.01 ? 96.09 98.03 ? 96.37 98.13 ? 99.49 98.65 ? 96.03 ? 99.03 97.35 ? 98.94 98.48 ? 99.78 99.88 ? 97.72 97.28 99.96 99.18 99.17 ? 98.79 ? 96.27 ? ? 96.27 96.33 96.86 97.89 ? 99.46 97.90 96.03 96.06 96.30 96.56 98.82 96.80 ? 98.55 94.84 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 98.11 ? 99.17 ? ? ? ? 96.42 ? ? ? 97.74 96.74 ? ? ? ? ? ? ? ? 98.47 ? ? ? ? ? ? ? 99.21 98.89 99.57 99.78 98.79 99.28 98.88 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.53 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 98.41 95.04 98.80 95.12 96.47 97.04 94.46 99.39 99.54 95.73 96.22 98.82 96.11 99.86 96.87 98.85 98.67 ? 97.23 ? 93.80 99.38 97.30 96.68 98.98 99.00 ? 98.50 ? 98.80 99.46 95.73 98.51 ? ? 98.33 98.79 97.18 96.58 99.28 97.82 99.46 99.75 95.57 ? ? 99.16 92.53 93.58 96.81 97.12 94.55 94.64 97.90 97.04 ? ? ? 97.43 ? 93.10 99.30 98.41 98.90 98.80 96.56 96.47 97.04 99.06 99.17 99.54 95.73 96.22 98.82 96.11 99.86 ? ? 98.67 95.03 99.17 ? 93.80 ? 97.30 ? 98.98 99.00 99.16 98.50 ? 98.80 99.46 95.73 98.51 ? ? 98.33 98.79 99.36 96.58 99.28 98.45 99.46 99.75 96.27 ? 97.14 99.16 92.31 ? 96.17 97.48 95.24 94.64 ? ? ? 95.56 ? 97.43 98.77 93.10 96.75 Evolutionary Computation Volume x, Number x BRKGAs for the WDP in Combinatorial Auctions Table 15: Best results for LG 1500/1500 instances. Inst. Best CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP in601 in602 in603 in604 in605 in606 in607 in608 in609 in610 in611 in612 in613 in614 in615 in616 in617 in618 in619 in620 in621 in622 in623 in624 in625 in626 in627 in628 in629 in630 in631 in632 in633 in634 in635 in636 in637 in638 in639 in640 in641 in642 in643 in644 in645 in646 in647 in648 in649 in650 in651 in652 in653 in654 in655 in656 in657 in658 in659 in660 in661 in662 in663 in664 in665 in666 in667 in668 108800.4450 105611.4760 105121.0220 107733.8050 109840.9840 107113.0670 113180.2840 105266.1070 109472.3320 113716.9650 106666.3438 109796.7400 107980.1570 108364.5859 110508.8281 109740.4922 113302.4340 111385.0810 107571.5930 110937.9750 106133.8500 107551.7370 109487.0290 104386.9790 109065.3594 114704.0340 108846.2344 108169.6953 107929.2600 105830.0620 116505.2440 104631.7140 105564.4000 108901.7300 112902.6340 106574.7480 107989.7280 112899.6320 108894.4550 108275.1328 109744.0625 114182.9688 104015.0240 108025.7490 105841.6720 107800.1030 107701.7109 105790.5900 107587.3710 103330.9010 103827.2970 107760.2480 113946.4766 111738.2310 111785.0640 112259.2750 112708.6560 110751.5340 106545.4270 112293.6080 113106.6290 108298.0790 104826.7800 112866.8650 113002.6720 106441.1562 104683.7500 107483.1580 58.25 24.41 39.04 50.52 52.38 37.26 43.74 50.50 3.23 32.91 10.31 54.31 71.82 49.66 37.36 44.02 45.99 47.03 43.20 59.54 41.62 55.58 42.38 48.61 43.83 50.12 37.55 42.91 40.10 54.00 31.18 52.88 65.72 47.86 39.75 48.82 33.07 30.01 43.77 53.59 56.06 40.41 13.04 60.10 37.99 33.71 51.25 37.28 40.30 45.80 55.97 28.48 34.60 35.91 44.33 43.93 37.47 38.17 39.45 39.96 30.29 58.18 52.39 42.89 39.05 46.49 65.93 45.33 95.76 93.92 92.40 96.29 93.23 92.47 90.23 96.26 96.71 93.89 94.57 ? 93.49 ? 97.15 88.30 92.27 94.81 97.72 92.13 ? 91.12 94.77 92.76 96.90 89.36 91.65 94.53 95.76 94.55 94.57 92.98 ? 94.31 92.44 92.64 92.70 97.48 92.99 96.04 98.77 91.12 94.62 98.22 92.97 93.84 90.90 ? 88.79 92.36 95.17 94.24 91.38 94.25 91.74 90.25 ? 91.70 94.76 98.65 97.20 97.41 95.93 95.93 98.78 ? 97.55 94.12 91.03 92.95 88.06 96.13 92.38 97.42 93.54 88.48 90.87 88.04 88.69 96.59 86.40 89.98 86.14 91.67 91.02 88.56 90.46 93.65 93.40 94.14 94.57 92.27 88.55 88.28 95.31 ? 94.64 93.68 94.02 90.76 90.90 91.85 86.62 91.03 91.77 88.95 94.68 91.48 92.27 90.13 91.75 93.57 90.05 94.90 93.95 96.66 94.52 93.79 94.21 97.48 89.41 89.29 88.65 96.67 93.86 91.29 96.16 91.81 87.06 91.26 95.40 91.67 94.75 91.88 91.77 93.41 96.77 95.78 92.54 96.29 94.98 98.23 93.54 97.88 95.77 95.86 ? ? 93.09 ? ? ? 93.78 99.93 94.97 95.07 93.40 98.49 94.99 95.69 ? 96.60 ? ? 97.16 99.65 96.91 95.18 98.72 93.34 92.44 98.23 99.01 92.88 95.35 ? ? ? 97.97 98.34 96.51 95.98 ? ? 95.70 96.86 98.85 97.48 ? 98.26 97.39 96.67 96.88 93.87 96.16 96.61 92.81 91.26 95.40 94.66 97.33 ? ? 98.89 ? ? ? 98.96 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 98.96 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 98.18 ? 97.57 98.96 ? ? ? ? ? 98.04 ? ? ? ? 98.92 ? ? 99.58 ? 97.96 ? ? ? ? ? ? 99.17 97.07 ? ? ? 99.59 ? ? ? 99.07 ? 97.48 ? 99.08 99.73 ? ? 99.03 ? ? 95.92 99.93 98.63 ? ? ? ? ? ? ? ? 96.80 99.03 99.72 ? ? ? 99.38 98.78 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 97.43 94.12 ? 98.04 ? 93.83 91.09 99.07 94.18 95.87 98.76 96.91 96.58 ? 92.40 95.39 91.75 95.53 97.72 97.96 98.14 96.71 96.90 ? 94.30 97.77 99.17 97.51 98.12 99.75 ? 98.28 94.20 93.80 94.72 97.76 99.01 97.48 ? 96.60 98.77 ? 97.97 99.03 96.08 ? 95.37 99.55 ? 97.02 ? 97.20 94.22 ? 96.13 94.21 95.65 ? ? 99.72 95.86 94.29 99.03 99.68 96.68 98.54 97.75 98.12 97.43 94.12 ? 98.04 ? 93.83 ? 99.07 95.55 98.04 98.76 94.91 ? ? 92.40 96.64 95.29 99.57 ? 96.75 98.14 97.53 96.90 ? 97.57 92.88 99.17 96.74 98.29 99.75 ? ? 94.02 93.80 94.72 93.89 99.01 97.48 ? 96.60 98.77 ? ? 98.25 97.25 ? 95.37 99.55 99.79 97.50 ? 96.19 94.22 ? 96.13 95.51 ? ? ? 98.65 97.63 94.29 92.33 99.68 96.68 98.54 97.75 98.12 Continue in next page. . . Evolutionary Computation Volume x, Number x 17 C.E. Andrade, F.K. Miyazawa, M.G.C. Resende, R.F. Toso Table 15: (continued). Inst. Best CORAL CPLEX RGRK BOMA CARA CALP GARA GALP SDRA SDLP in669 in670 in671 in672 in673 in674 in675 in676 in677 in678 in679 in680 in681 in682 in683 in684 in685 in686 in687 in688 in689 in690 in691 in692 in693 in694 in695 in696 in697 in698 in699 in700 108163.4690 110200.8160 109306.8438 107534.8870 112320.2500 109558.2344 108131.9880 107052.1910 107831.5370 102422.8290 107982.4560 107500.5000 105237.2870 107948.1260 107777.6130 114153.7410 106686.6160 106364.3580 108301.4710 112012.5703 105968.1680 108489.7109 105564.6090 109226.0700 106719.6950 114477.0540 110240.9860 104559.9530 105958.6570 105463.0312 107132.3340 106730.6770 42.49 50.35 48.13 43.05 44.61 37.01 47.04 37.62 45.33 29.45 48.90 44.67 53.94 38.39 7.06 62.07 39.69 19.52 44.81 50.12 48.45 34.23 37.21 44.39 31.31 47.90 14.09 39.47 23.47 26.21 41.24 45.46 97.80 94.90 99.75 93.33 92.20 91.87 ? 94.64 96.19 ? 90.90 96.69 93.19 97.33 95.19 91.14 94.83 99.45 97.06 93.49 92.72 92.05 93.06 93.71 97.08 89.45 91.30 ? 98.78 95.12 96.37 95.37 93.65 92.73 ? 95.58 92.34 87.59 92.14 88.05 97.47 95.83 92.06 91.50 92.10 89.67 93.47 85.74 92.42 92.48 94.98 94.55 94.96 92.90 96.78 91.40 93.34 94.44 93.91 95.00 92.49 92.14 96.85 95.11 96.78 96.53 ? 95.58 ? ? 97.81 96.10 99.68 96.87 99.21 ? 99.85 98.25 96.08 94.52 92.74 98.55 97.05 ? 97.70 ? 96.78 97.15 97.58 94.44 93.91 98.94 98.46 ? 98.42 95.11 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.53 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.68 ? 98.61 ? ? ? ? ? 97.71 99.45 ? 99.83 ? ? ? ? 99.56 96.94 98.04 ? ? ? 99.26 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 99.53 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 95.71 99.98 99.75 96.40 98.43 95.40 ? ? 97.03 ? 96.35 98.92 ? 98.25 98.25 92.55 97.81 97.70 99.10 95.27 98.39 97.02 98.50 98.99 99.56 93.66 ? 99.43 98.78 97.86 99.14 97.09 94.23 99.85 99.75 95.58 98.43 95.40 ? ? 97.22 ? 96.11 98.92 ? 99.93 98.25 94.26 97.81 97.70 99.10 97.60 98.39 97.02 98.50 97.40 97.08 93.66 ? 99.43 98.78 97.77 99.14 94.31 References Benjamini, Y. and Hochberg, Y. (1995). Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society. Series B (Methodological), 57(1):289–300. Chu, P. C. and Beasley, J. E. (1998). A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4:63–86. 18 Evolutionary Computation Volume x, Number x
© Copyright 2024 ExpyDoc
