Euclidean Instances in 10**7 by 10**7 Square Sample Size = 10,000 OPT - optimal tour length SUB - subtour relaxation lower bound GAP - 100 * (OPT - SUB) / SUB Mean and Standard Deviation ---------------------------------------------------------------------- n OPT Stdev SUB Stdev GAP Stdev ---------------------------------------------------------------------- 10 0.908545 0.107356 0.908472 0.107309 0.007621 0.081571 20 0.857779 0.067577 0.856238 0.066892 0.175826 0.452534 30 0.832562 0.051585 0.829225 0.050901 0.400783 0.649196 40 0.816966 0.041497 0.812358 0.041069 0.568347 0.699221 50 0.805676 0.035669 0.800428 0.035415 0.657735 0.665083 60 0.796584 0.031486 0.791128 0.031375 0.692128 0.620783 70 0.789592 0.028496 0.784004 0.028384 0.714694 0.567225 80 0.784570 0.026299 0.778789 0.026310 0.744533 0.530751 90 0.780278 0.024416 0.774545 0.024366 0.742016 0.493486 100 0.776469 0.023001 0.770554 0.022989 0.769293 0.468819 110 0.773085 0.021682 0.767132 0.021662 0.777509 0.448874 120 0.770532 0.020582 0.764527 0.020646 0.787151 0.428988 130 0.768130 0.019705 0.762087 0.019718 0.794383 0.411938 140 0.765833 0.018951 0.759812 0.019022 0.793927 0.390224 150 0.763660 0.017895 0.757665 0.017973 0.792673 0.373635 160 0.762260 0.017347 0.756220 0.017414 0.799932 0.361457 170 0.760623 0.016990 0.754582 0.017031 0.801656 0.350326 180 0.759100 0.016052 0.753069 0.016105 0.801815 0.333207 190 0.757604 0.015734 0.751580 0.015849 0.802644 0.324448 200 0.756354 0.015257 0.750346 0.015344 0.801847 0.323111 210 0.755384 0.014950 0.749387 0.015061 0.801355 0.306051 220 0.754279 0.014519 0.748308 0.014601 0.798929 0.299757 230 0.753442 0.013998 0.747456 0.014089 0.801821 0.286937 240 0.752484 0.013593 0.746518 0.013680 0.799999 0.286031 250 0.751430 0.013399 0.745456 0.013512 0.802316 0.275796 260 0.750734 0.012929 0.744761 0.013030 0.802875 0.273061 270 0.749983 0.012920 0.744080 0.013059 0.794294 0.263246 280 0.749418 0.012576 0.743505 0.012697 0.796210 0.261176 290 0.748538 0.012364 0.742642 0.012452 0.794571 0.255062 300 0.747763 0.012152 0.741872 0.012255 0.794748 0.247436 310 0.747142 0.011985 0.741272 0.012084 0.792654 0.242922 320 0.746716 0.011537 0.740868 0.011623 0.790041 0.238375 330 0.746141 0.011536 0.740296 0.011674 0.790363 0.234012 340 0.745499 0.011363 0.739658 0.011462 0.790281 0.228080 350 0.744947 0.011118 0.739096 0.011240 0.792427 0.227764 360 0.744602 0.010966 0.738775 0.011085 0.789495 0.225497 370 0.744283 0.010841 0.738500 0.010930 0.783743 0.218718 380 0.743686 0.010605 0.737883 0.010703 0.786962 0.210646 390 0.743194 0.010437 0.737402 0.010531 0.785936 0.210361 400 0.742844 0.010377 0.737088 0.010509 0.781647 0.208415 410 0.742430 0.010218 0.736675 0.010316 0.781783 0.203678 420 0.742087 0.010188 0.736354 0.010277 0.779056 0.201800 430 0.741840 0.009957 0.736124 0.010057 0.776955 0.198173 440 0.741354 0.009842 0.735616 0.009933 0.780591 0.195461 450 0.741119 0.009721 0.735384 0.009819 0.780483 0.192814 460 0.740631 0.009581 0.734909 0.009698 0.779108 0.191026 470 0.740203 0.009517 0.734496 0.009600 0.777343 0.186416 480 0.739940 0.009441 0.734259 0.009528 0.774238 0.183864 490 0.739776 0.009366 0.734089 0.009457 0.775157 0.183119 500 0.739454 0.009135 0.733800 0.009249 0.771098 0.180584 510 0.739001 0.009120 0.733328 0.009217 0.773984 0.179398 520 0.738942 0.008984 0.733267 0.009105 0.774381 0.177809 530 0.738671 0.008790 0.732982 0.008891 0.776516 0.177546 540 0.738426 0.008786 0.732777 0.008901 0.771308 0.172671 550 0.738228 0.008594 0.732593 0.008713 0.769600 0.171794 560 0.737927 0.008618 0.732304 0.008733 0.768310 0.169973 570 0.737550 0.008609 0.731929 0.008693 0.768349 0.165706 580 0.737309 0.008469 0.731704 0.008554 0.766389 0.166086 590 0.737176 0.008447 0.731568 0.008534 0.766898 0.164831 600 0.736941 0.008316 0.731332 0.008421 0.767305 0.161523 610 0.736722 0.008266 0.731119 0.008354 0.766696 0.162250 600 0.736941 0.008316 0.731332 0.008421 0.767305 0.161523 610 0.736722 0.008266 0.731119 0.008354 0.766696 0.162250 620 0.736622 0.008162 0.731024 0.008257 0.766247 0.159258 630 0.736276 0.008114 0.730706 0.008226 0.762649 0.158331 640 0.736087 0.008029 0.730517 0.008137 0.762905 0.158187 650 0.736006 0.007959 0.730433 0.008047 0.763248 0.154498 660 0.735840 0.007934 0.730280 0.008024 0.761692 0.151777 670 0.735643 0.007947 0.730095 0.008043 0.760231 0.150690 680 0.735440 0.007807 0.729907 0.007886 0.758289 0.150989 690 0.735132 0.007696 0.729597 0.007808 0.759038 0.149818 700 0.734990 0.007623 0.729461 0.007718 0.758251 0.148447 710 0.734886 0.007658 0.729361 0.007750 0.757834 0.144645 720 0.734792 0.007470 0.729275 0.007565 0.756718 0.144493 730 0.734597 0.007384 0.729078 0.007488 0.757202 0.146766 740 0.734470 0.007399 0.728969 0.007485 0.754901 0.143379 750 0.734292 0.007410 0.728792 0.007510 0.755056 0.140195 760 0.734076 0.007265 0.728576 0.007359 0.755164 0.141414 770 0.733928 0.007185 0.728422 0.007252 0.756193 0.141882 780 0.733840 0.007140 0.728368 0.007221 0.751526 0.139232 790 0.733802 0.007078 0.728324 0.007175 0.752418 0.138078 800 0.733575 0.007164 0.728103 0.007272 0.751828 0.135943 810 0.733376 0.007096 0.727927 0.007178 0.748934 0.136392 820 0.733355 0.007093 0.727886 0.007182 0.751644 0.135936 830 0.733174 0.006972 0.727730 0.007043 0.748246 0.132655 840 0.733071 0.006873 0.727626 0.006946 0.748575 0.134804 850 0.732928 0.006901 0.727490 0.006988 0.747756 0.132372 860 0.732743 0.006765 0.727307 0.006865 0.747754 0.132363 870 0.732640 0.006794 0.727195 0.006878 0.748965 0.128861 880 0.732512 0.006716 0.727091 0.006804 0.745795 0.130124 890 0.732338 0.006705 0.726917 0.006788 0.745921 0.127026 900 0.732111 0.006694 0.726686 0.006779 0.746794 0.126363 910 0.732156 0.006613 0.726746 0.006691 0.744639 0.126666 920 0.732046 0.006609 0.726623 0.006695 0.746626 0.126674 930 0.731916 0.006551 0.726521 0.006645 0.742767 0.125800 940 0.731890 0.006559 0.726485 0.006641 0.744227 0.124628 950 0.731660 0.006492 0.726268 0.006565 0.742605 0.123865 960 0.731708 0.006443 0.726314 0.006526 0.742819 0.123972 970 0.731506 0.006461 0.726120 0.006550 0.741996 0.122688 980 0.731474 0.006347 0.726086 0.006420 0.742391 0.122212 990 0.731362 0.006407 0.725964 0.006470 0.743800 0.120841 1000 0.731223 0.006317 0.725865 0.006392 0.738381 0.120503 1100 0.724960 0.006156 1200 0.724105 0.005854 1300 0.723625 0.005555 1400 0.722846 0.005329 1500 0.722444 0.005128 1600 0.721884 0.005021 1700 0.721517 0.004801 1800 0.721110 0.004668 1900 0.720691 0.004542 2000 0.725538 0.004371 0.720421 0.004437 0.710427 0.079824 2100 0.720064 0.004369 2200 0.719812 0.004164 2300 0.719559 0.004130 2400 0.719266 0.004059 2500 0.719035 0.003945 2600 0.718799 0.003910 2700 0.718640 0.003791 2800 0.718470 0.003747 2900 0.718217 0.003684 3000 0.718123 0.003601 3100 0.717903 0.003557 3200 0.717790 0.003484 3300 0.717545 0.003418 3400 0.717363 0.003382 3500 0.717334 0.003285 3600 0.717139 0.003288 3700 0.717075 0.003227 3800 0.716909 0.003191 3900 0.716716 0.003147 4000 0.716660 0.003128 4100 0.716553 0.003079 4200 0.716463 0.002996 4300 0.716424 0.003016 4400 0.716210 0.002948 4500 0.716132 0.002925 4600 0.716059 0.002899 4700 0.715956 0.002876 4800 0.715849 0.002858 4900 0.715759 0.002837 5000 0.715720 0.002778 5100 0.715588 0.002741 5200 0.715563 0.002686 5300 0.715466 0.002669 5400 0.715426 0.002637 5500 0.715330 0.002630 5600 0.715248 0.002625 5700 0.715173 0.002619 5800 0.715180 0.002581 5900 0.715102 0.002559 6000 0.715036 0.002523 6100 0.714957 0.002513 6200 0.714950 0.002466 6300 0.714848 0.002450 6400 0.714835 0.002449 6500 0.714742 0.002423 6600 0.714697 0.002430 6700 0.714627 0.002425 6800 0.714612 0.002357 6900 0.714562 0.002364 7000 0.714467 0.002303 7100 0.714444 0.002312 7200 0.714422 0.002312 7300 0.714356 0.002241 7400 0.714298 0.002264 7500 0.714299 0.002270 7600 0.714218 0.002246 7700 0.714139 0.002248 7800 0.714158 0.002206 7900 0.714127 0.002171 8000 0.714049 0.002203 8100 0.714062 0.002183 8200 0.714005 0.002140 8300 0.713974 0.002153 8400 0.713901 0.002089 8500 0.713902 0.002098 8600 0.713820 0.002103 8700 0.713786 0.002072 8800 0.713758 0.002084 8900 0.713722 0.002055 9000 0.713720 0.002014 9100 0.713719 0.002034 9200 0.713674 0.002020 9300 0.713604 0.002016 9400 0.713612 0.002033 9500 0.713542 0.001994 9600 0.713525 0.001980 9700 0.713491 0.001944 9800 0.713475 0.001960 9900 0.713444 0.001935 10000 0.713420 0.001945 20000 0.711816 0.001367 30000 0.711083 0.001110 40000 0.710672 0.000961 50000 0.710376 0.000869 60000 0.710175 0.000789 70000 0.710002 0.000718 80000 0.709890 0.000684 90000 0.709769 0.000637 100000 0.709670 0.000607 ---------------------------------------------------------------------- ---------------------------------------------------------------------- Sample size = 1,000 for million-city instances 1000000 0.708511 0.000198