New Results  Filipe Brandão's Homepage

Arc Flow Formulation (w/ graph compression) Results: WAE/GAU Card

Results for Brandão, F. (2012). Bin Packing and Related Problems: Pattern-Based Approaches. Master’s thesis
17,487 benchmark instances solved in 5 days (less than 25 seconds per instance, on average).
Computer: 2 x Quad-Core Intel Xeon at 2.66GHz, Mac OS X 10.8.0, 16 GBytes of memory
Solver: Gurobi 5.0.0, Threads = 1 (single thread), Presolve = 1 (conservative),
Method = 2 (interior point methods), MIPFocus = 1 (feasible solutions),
Heuristics = 1, MIPGap = 0, MIPGapAbs = 1-10^5, Download Logs

NameTypeDescription#Solved#Total
Bin PackingBPP1D Bin-Packing Problems from FALKENAUER (1996).160 160
SchollBPP1D Bin-Packing Problems from SCHOLL/KLEIN/JUERGENS (1997).1210 1210
Hard28BPPThe 28 VERY hard BPP instances of J. Schoenfield (with m from 140 to 200).28 28
SCH/WAEBPP1D Bin-Packing Problems from SCHWERIN/WAESCHER (1998).200 200
WAE/GAUBPP1D Bin-Packing Problems from WAESCHER/GAU (1996).17 17
Cutting StockCSP1D Bin-Packing Problems from FALKENAUER (1996) [demand x 10^6].160 160
CutgenCSPCUTGEN (Gau and Wascher, 1995).1800 1800
FiberCSPInstances taken from a real application in a paper tube industry in Japan.39 39
Bin Packing CardCardInstances from FALKENAUER (1996) [with cardinality constraints].720 720
Scholl CardCard1D Bin-Packing Problems from SCHOLL/KLEIN/JUERGENS (1997) [with cardinality constraints].3748 3748
Hard28 CardCardThe 28 VERY hard BPP instances of J. Schoenfield (with m from 140 to 200) [with cardinality constraints].56 56
SCH/WAE CardCard1D Bin-Packing Problems from SCHWERIN/WAESCHER (1998) [with cardinality constraints].1000 1000
WAE/GAU CardCard1D Bin-Packing Problems from WAESCHER/GAU (1996) [with cardinality constraints].131 131
Cutting Stock CardCardInstances from FALKENAUER (1996) [demand x 10^6; with cardinality constraints].320 320
Cutgen CardCardCUTGEN (Gau and Wascher, 1995) [with cardinality constraints].7299 7299
Fiber CardCardInstances taken from a real applications in a paper tube industry in Japan [with cardinality constraints].279 279
Two-Constraint BPP2CBPTwo-Constraint Bin Packing instances of Spieksma/Caprara/Toth.320 400
total run time
graph reduction (vertices)graph reduction (arcs)
nameWCnmzlb_lplb_splb_crd#v1#a1#v2#a2#v3#a3#v4#a4%v%an_bbt_ppt_lpt_ipttz2ffd2bfda_2ffda_2bfdr_2ffdr_2bfd
WAE_GAU110000.06.6159.051.1 31.931.5715.2831.46 39194.6542334.1638126.41740197.87927.2117646.47406.4116367.618.921.5 0.334.90194.99971.721171.61  31.933.2233.221.331.330.08 0.08
WAE_GAU210000.06.0134.849.5 30.430.0816.4129.74 34204.5493874.1582554.81590574.86115.979900.45616.378588.916.415.9 1.094.28120.16329.66454.11  30.431.6831.681.291.290.07 0.07
nameWCnmzlb_lplb_splb_crd#v1#a1#v2#a2#v3#a3#v4#a4%v%an_bbt_ppt_lpt_ipttz2ffd2bfda_2ffda_2bfdr_2ffdr_2bfd
TEST_510000511457 2827.9927.9922.80 2576119641426635967761014541013590089893.54.6 321.400.455.557.40  283030220.07 0.07
TEST_510000411457 2928.5027.9928.50 17173115754180606442620530351234131112.02.7 00.850.070.311.23  293232330.10 0.10
TEST_510000311457 3838.0027.9938.00 88363299947385110097178799635570.71.7 00.210.010.020.24  383838000.00 0.00
TEST_510000211457 5757.0027.9957.00 152132043339684011634041160.33.6 00.020.000.000.02  575757000.00 0.00
TEST_221000045733 1514.2514.0014.25 11543396735331212321123310501218051.02.0 00.240.020.050.31  151616110.07 0.07
TEST_221000035733 1919.0014.0019.00 43119880108842302699342362100.82.1 00.050.000.010.06  191919000.00 0.00
TEST_221000025733 2928.5014.0028.50 565114211412294671944680.76.0 00.020.000.000.02  292929000.00 0.00
TEST_54100001114456 1414.0014.0013.09 79681110561912320353410327224283675602152136500327.033.0 011.03687.112000.952699.09  141717330.21 0.21
TEST_54100001014456 1514.4014.0014.40 70625102089011562603192160178092933771694229102024.028.5 09.82342.381491.871844.07  151818330.20 0.20
TEST_5410000914456 1616.0014.0016.00 6149892426410685752938418131722173861230221508520.023.3 08.50189.17771.87969.54  161919330.19 0.19
TEST_5410000814456 1818.0014.0018.00 5231081351396671426423219574145766862714340116.517.6 07.1065.71253.21326.02  182020220.11 0.11
TEST_5410000714456 2120.5714.0020.57 43074686851848773229824959457606250557383411.710.7 05.6615.5654.6175.83  212222110.05 0.05
TEST_5410000614456 2424.0014.0024.00 3380353953770959618911232490210071762191335.23.5 04.221.072.617.90  242525110.04 0.04
TEST_5410000514456 2928.8014.0028.80 245233653185378251391922644300926019851.10.5 02.850.040.092.98  292929000.00 0.00
TEST_5410000414456 3636.0014.0036.00 152511649422739546823483201020573900.40.2 01.290.000.011.30  363636000.00 0.00
TEST_5410000314456 4848.0014.0048.00 68833425653466127422196591222200.30.6 00.220.000.010.23  484848000.00 0.00
TEST_5410000214456 7272.0014.0072.00 135729883230673411333141130.33.8 00.020.000.000.02  727272000.00 0.00
TEST_55a100001014252 1515.0015.0014.20 648718743989887842722224156542769021488827476723.031.4 08.46425.22914.141347.82  151818330.20 0.20
TEST_55a10000914252 1615.7815.0015.78 565977968129193432522304123262057571150920357620.325.5 07.33147.13572.43726.89  161919330.19 0.19
TEST_55a10000814252 1817.7515.0017.75 4816970567483637422820848577131109777212906416.118.3 06.1143.61240.23289.95  182020220.11 0.11
TEST_55a10000714252 2120.2915.0020.29 39589596915735758198925347826126840335943510.210.0 04.838.7041.2654.79  212222110.05 0.05
TEST_55a10000614252 2423.6715.0023.67 3086846516061191116272461824144531205129783.92.8 03.590.542.026.15  242525110.04 0.04
TEST_55a10000514252 2928.4015.0028.40 22039303906446871115357049817351769290.80.3 02.310.010.042.36  292929000.00 0.00
TEST_55a10000414252 3635.5015.0035.50 13161133146218503543830295912643900.50.3 01.020.000.011.03  363636000.00 0.00
TEST_55a10000314252 4847.3315.0047.33 59052858244177105126174520171920.30.7 00.180.000.010.19  484848000.00 0.00
TEST_55a10000214252 7171.0015.0071.00 118726032797582310530741050.34.0 00.020.000.000.02  717171000.00 0.00
TEST_55b100001223964 2019.9919.9919.92 87803166453718531625195255274246397782652463746830.238.3 018.031444.1110870.5712332.71  202525550.25 0.25
TEST_55b100001123964 2221.7319.9921.73 78837155695517545094908299231315346582224453238828.234.2 016.21557.934929.455503.59  222626440.18 0.18
TEST_55b100001023964 2423.9019.9923.90 69831143591616424294581112185624184061768941611725.329.0 014.38372.262653.603040.24  242727330.12 0.12
TEST_55b10000923964 2726.5619.9926.56 60785129774815131424202462143282963701343229408622.122.7 012.33206.561137.771356.66  272929220.07 0.07
TEST_55b10000823964 3029.8819.9929.88 516991137640136179537578329672178539873717622316.915.5 010.2075.87375.13461.20  303232220.07 0.07
TEST_55b10000723964 3534.1419.9934.14 425739508481183545323279254608021645637806510.78.2 08.0016.4354.8679.29  353636110.03 0.03
TEST_55b10000623964 4039.8319.9939.83 3340773336097422526149962149189691426172384.32.4 05.880.832.699.40  404141110.03 0.03
TEST_55b10000523964 4847.8019.9947.80 242014805687178891867944623234621713470.90.3 03.880.020.083.98  484848000.00 0.00
TEST_55b10000423964 6059.7519.9959.75 149592134553593599022553471082564190.40.2 01.720.000.011.73  606060000.00 0.00
TEST_55b10000323964 8079.6719.9979.67 69354593776184184435219659212420.30.5 00.320.000.010.33  808080000.00 0.00
TEST_55b10000223964 120119.5019.99119.50 159837274212895513038241300.33.5 00.030.000.000.03  120120120000.00 0.00
TEST_581000059138 2020.0020.0018.20 22121130736176709439912747399543933482.02.6 00.860.110.961.93  202323330.15 0.15
TEST_581000049138 2322.7520.0022.75 140146373992759221229294137215810851.11.7 00.420.020.050.49  232525220.09 0.09
TEST_581000039138 3130.3320.0030.33 6079150841747737880127441412640.71.8 00.080.000.010.09  313131000.00 0.00
TEST_581000029138 4645.5020.0045.50 749151815133046772234770.55.1 00.020.000.000.02  464646000.00 0.00
TEST_651000046035 1615.0015.0015.00 102573602648125111762278141215211471.53.2 00.220.020.050.29  161717110.06 0.06
TEST_651000036035 2020.0015.0020.00 4355106591226726483110402392540.92.4 00.060.000.010.07  202020000.00 0.00
TEST_651000026035 3030.0015.0030.00 624127012792580712054710.65.6 00.020.000.000.02  303030000.00 0.00
TEST_68100001416346 1212.0012.0011.64 97844125801713474943757317313185225023055052064031.241.4 013.281318.2927513.5628845.13  121616440.33 0.33
TEST_68100001316346 1312.5412.0012.54 90107119730812943653605824272614579472641845592229.338.1 012.17844.433321.464178.06  131616330.23 0.23
TEST_68100001216346 1413.5812.0013.58 82189112925012340653433002227803865612193238447226.734.0 011.13583.852210.582805.56  141717330.21 0.21
TEST_68100001116346 1514.8212.0014.82 74090105238911651003234409190793134641820131126224.629.6 010.05374.151662.722046.92  151818330.20 0.20
TEST_68100001016346 1716.3012.0016.30 6581196502310857803004961155772369721452723443122.124.3 08.81231.05588.58828.44  171919220.12 0.12
TEST_6810000916346 1918.1112.0018.11 573608653219942102739021116071580651048315536418.318.0 07.4886.08303.49397.05  192020110.05 0.05
TEST_6810000816346 2120.3812.0020.38 48751750236887182242709872948487662878248212.911.0 06.0931.8885.03123.00  212222110.05 0.05
TEST_6810000716346 2423.2912.0023.29 3999961589176073720573673500316102618294826.54.8 04.723.098.1615.97  242424000.00 0.00
TEST_6810000616346 2827.1712.0027.17 3112546035161251116231231179722267259462.21.3 03.450.150.504.10  282828000.00 0.00
TEST_6810000516346 3332.6012.0032.60 22154281672421964108129239313541316920.60.2 02.140.010.022.17  333333000.00 0.00
TEST_6810000416346 4140.7512.0040.75 13106113631185940459299247761443080.30.3 00.830.000.010.84  414141000.00 0.00
TEST_6810000316346 5554.3312.0054.33 5646221363208275008156464181780.30.8 00.130.000.010.14  555555000.00 0.00
TEST_6810000216346 8281.5012.0081.50 992210421964512932714930.44.4 00.020.000.000.02  828282000.00 0.00
TEST_75100001822846 1313.0013.0012.67 144870162374216592164652434487696093274802160748133.137.4 016.683043.9713782.6316843.28  131818550.38 0.38
TEST_75100001722846 1413.4113.0013.41 135725155642216010384487048442885589854351455711632.135.8 015.571909.711771.183696.46  141919550.36 0.36
TEST_75100001622846 1514.2513.0014.25 126546148548015392644310916390625042793828550242530.333.8 014.591294.961513.812823.36  151919440.27 0.27
TEST_75100001522846 1615.2013.0015.20 117334141025514732284122043352064516543442944980229.331.9 013.611054.131339.452407.19  162020440.25 0.25
TEST_75100001422846 1716.2913.0016.29 108089133019714023513918721305403945952988739303727.729.5 012.59778.203470.244261.03  172121440.24 0.24
TEST_75100001322846 1817.5413.0017.54 98811124482313260813699363249393344622434933305224.626.8 011.48673.931769.202454.61  182121330.17 0.17
TEST_75100001222846 1919.0013.0019.00 89500115325012435913461432204382818191985928044522.224.3 010.47480.041981.472471.98  192222330.16 0.16
TEST_75100001122846 2120.7313.0020.73 80156105504611544473203628176902389421710223753621.322.5 09.33310.47831.841151.64  212424330.14 0.14
TEST_75100001022846 2322.8013.0022.80 7077995046410589162926738155511971411485519554821.020.6 08.25123.88705.44837.57  232525220.09 0.09
TEST_7510000922846 2625.3313.0025.33 613698396269571012631090123871451711157214340218.917.1 07.0565.59318.00390.64  262727110.04 0.04
TEST_7510000822846 2928.5013.0028.50 51926722252848677231575481518536272868350014.011.6 05.7621.5282.83110.11  293030110.03 0.03
TEST_7510000722846 3332.5713.0032.57 4245059246772769019629474051345783185327227.55.5 04.482.647.3114.43  333333000.00 0.00
TEST_7510000622846 3838.0013.0038.00 3294444532658884715571321297794375767002.31.5 03.310.180.363.85  383939110.03 0.03
TEST_7510000522846 4645.6013.0045.60 23413276109409400104808339313461357250.60.3 02.060.010.022.09  464646000.00 0.00
TEST_7510000422846 5757.0013.0057.00 13876113032183214451708226685352740.30.2 00.820.000.010.83  575757000.00 0.00
TEST_7510000322846 7676.0013.0076.00 591622072313797299814442591510.20.7 00.140.000.000.14  767676000.00 0.00
TEST_7510000222846 114114.0013.00114.00 982209221944516932714930.44.4 00.020.000.000.02  114114114000.00 0.00
TEST_841000069263 1615.9815.9815.33 34519469128613579162724844105549534815343110.111.4 03.906.7529.0039.65  162020440.25 0.25
TEST_841000059263 1918.4015.9818.40 2653135621050677213166921915178971147161834.34.5 02.870.804.227.89  192121220.11 0.11
TEST_841000049263 2323.0015.9823.00 18271214184361062899766655432428734801.61.6 01.780.070.152.00  232424110.04 0.04
TEST_841000039263 3130.6715.9830.67 98404805075289178948226739633760.60.8 00.340.000.020.36  313131000.00 0.00
TEST_841000029263 4646.0015.9846.00 176638054058838912737341270.23.3 00.030.000.000.03  464646000.00 0.00
TEST_95100001015363 1616.0016.0015.30 69624114891613041243617916160812731521526927058421.923.6 010.73439.871460.411911.01  162121550.31 0.31
TEST_9510000915363 1717.0016.0017.00 61153103138311948833298843135962218761285321955121.021.3 09.40205.961265.601480.96  172121440.24 0.24
TEST_9510000815363 2019.1216.0019.12 5250390342110752912948997109201649591007016261319.218.0 07.9775.28456.22539.47  202222220.10 0.10
TEST_9510000715363 2221.8616.0021.86 43681763191943367256256369959738961639523314.112.5 06.4023.79100.28130.47  222424220.09 0.09
TEST_9510000615363 2625.5016.0025.50 3470360483579296221213532977321782306304646.65.0 04.803.3413.5921.73  262727110.04 0.04
TEST_9510000515363 3130.6016.0030.60 255864189406106321589032910539743341231.71.0 03.290.100.233.62  313131000.00 0.00
TEST_9510000415363 3938.2516.0038.25 163482029013383268468573741229574250.30.2 01.610.000.011.62  393939000.00 0.00
TEST_9510000315363 5151.0016.0051.00 76774508673306176344227694262540.30.6 00.310.000.010.32  515151000.00 0.00
TEST_9510000215363 7776.5016.0076.50 164937024072854812637141270.23.4 00.030.000.000.03  777777000.00 0.00
TEST_97100001011942 1211.9911.9911.90 676057043867807032130582158831927001491019014522.127.0 06.37213.25873.661093.28  121414220.17 0.17
TEST_9710000911942 1413.2211.9913.22 586726395477247251971653115841380051069313564618.221.2 05.4682.26293.12380.84  141414000.00 0.00
TEST_9710000811942 1514.8811.9914.88 49737563393657348177861579218602370368386914.114.9 04.5425.0993.74123.37  151515000.00 0.00
TEST_9710000711942 1717.0011.9917.00 4080047398157652315454274377402803610384098.88.1 03.624.1620.3628.14  171717000.00 0.00
TEST_9710000611942 2019.8311.9919.83 318613679044782541260690161111177108098503.42.7 02.720.491.634.84  202020000.00 0.00
TEST_9710000511942 2423.8011.9923.80 22924242218356122908614482205323714441.00.6 01.810.020.081.91  242424000.00 0.00
TEST_9710000411942 3029.7511.9929.75 14010100486160933394332245757583350.40.3 00.730.000.010.74  303030000.00 0.00
TEST_9710000311942 4039.6711.9939.67 5767188012528057827146434201730.30.9 00.110.000.010.12  404040000.00 0.00
TEST_9710000211942 6059.5011.9959.50 862179718413755862504860.54.8 00.020.000.000.02  606060000.00 0.00
nameWCnmzlb_lplb_splb_crd#v1#a1#v2#a2#v3#a3#v4#a4%v%an_bbt_ppt_lpt_ipttz2ffd2bfda_2ffda_2bfdr_2ffdr_2bfd
TEST_141000059647 2323.0023.0019.20 24970204931290736736463980606456851682.32.5 371.490.260.932.68  232525220.09 0.09
TEST_141000049647 2424.0023.0024.00 16565103003162462394797396199620915951.31.5 00.740.030.110.88  242727330.12 0.12
TEST_141000039647 3232.0023.0032.00 8009235393056168643126519393310.51.4 00.140.000.010.15  323333110.03 0.03
TEST_141000029647 4848.0023.0048.00 1086224022854638952784960.44.3 00.020.000.000.02  484848000.00 0.00
TEST_3010000511155 2727.0027.0022.20 244901735752347725941391225856277476243.24.4 01.220.302.333.85  273030330.11 0.11
TEST_3010000411155 2827.7527.0027.75 16266101168154854378344465280028624251.82.4 00.720.050.160.93  283232440.14 0.14
TEST_3010000311155 3737.0027.0037.00 8324296604181496640157765585580.71.9 00.190.010.010.21  373737000.00 0.00
TEST_3010000211155 5655.5027.0055.50 146630393116633911132541110.33.7 00.020.000.000.02  565656000.00 0.00
TEST_44100001216456 1414.0014.0013.67 87975159503317556424930367275454461742639444253330.027.7 015.89947.522153.723117.13  141818440.29 0.29
TEST_44100001116456 1514.9114.0014.91 79449147247616414254596428227203634732161736008327.224.5 014.20607.322455.883077.40  151919440.27 0.27
TEST_44100001016456 1716.4014.0016.40 70759133839715158184228515177662804861671527738923.620.7 012.41371.141143.661527.21  172020330.18 0.18
TEST_4410000916456 1918.2214.0018.22 61911119095813769723821080135191996421248219676520.216.5 010.61152.46723.84886.91  192121220.11 0.11
TEST_4410000816456 2120.5014.0020.50 529101028250122263433676989217122423817511971715.511.6 08.7770.98244.51324.26  212323220.10 0.10
TEST_4410000716456 2423.4314.0023.43 43769847290104986928594905186568504245544989.76.4 06.8611.8138.0656.73  242525110.04 0.04
TEST_4410000616456 2827.3314.0027.33 3450964566285571922880822107147301415129664.12.0 05.070.622.247.93  282828000.00 0.00
TEST_4410000516456 3332.8014.0032.80 251554208676304881631533592250323015550.90.4 03.330.020.073.42  333333000.00 0.00
TEST_4410000416456 4141.0014.0041.00 15744182910308152767726305966443480.30.2 01.450.000.011.46  414141000.00 0.00
TEST_4410000316456 5554.6714.0054.67 71413536255190131460193582202130.30.6 00.240.000.010.25  555555000.00 0.00
TEST_4410000216456 8282.0014.0082.00 139430253230669711333141130.33.7 00.020.000.000.02  828282000.00 0.00
TEST_49100001314143 1110.9910.9910.85 96963124438413219123694282274553489672639834591127.227.8 011.73946.311421.372379.41  111414330.27 0.27
TEST_49100001214143 1211.7510.9911.75 87968115598312424683464983236662871722262728428525.724.6 010.53452.381438.841901.75  121515330.25 0.25
TEST_49100001114143 1312.8210.9912.82 78877105972311551733212315184932203891760921795822.320.6 09.32322.08901.241232.64  131515220.15 0.15
TEST_49100001014143 1514.1010.9914.10 6969395379710582222930855137671584571298815631118.616.4 08.04131.84464.93604.81  151616110.07 0.07
TEST_4910000914143 1615.6710.9915.67 60421837638951076261894810167105050941010310615.612.3 06.7755.34173.15235.26  161717110.06 0.06
TEST_4910000814143 1817.6210.9917.62 51067710748833199227501264745698556245497611.07.7 05.4513.5636.7155.72  181919110.06 0.06
TEST_4910000714143 2120.1410.9920.14 4163857196070328618952562811202332096185765.03.2 04.241.396.1011.73  212121000.00 0.00
TEST_4910000614143 2423.5010.9923.50 321454184515576461469453941489752138951.60.9 03.060.100.253.41  242424000.00 0.00
TEST_4910000514143 2928.2010.9928.20 2260224775936784293823934311681015700.40.2 01.830.010.021.86  292929000.00 0.00
TEST_4910000414143 3635.2510.9935.25 1307698424158175388622219673332560.30.3 00.710.000.010.72  363636000.00 0.00
TEST_4910000314143 4747.0010.9947.00 5501189422606560070139413101450.20.8 00.120.000.000.12  474747000.00 0.00
TEST_4910000214143 7170.5010.9970.50 873184619223944872534870.54.7 00.020.000.000.02  717171000.00 0.00
TEST_821000048648 2423.9923.9721.50 133235335873844174400349167818813491.42.5 00.340.020.380.74  242727330.12 0.12
TEST_821000038648 2928.6723.9728.67 5957153661830440060140591504060.82.6 00.080.010.010.10  293030110.03 0.03
TEST_821000028648 4343.0023.9743.00 95619571990402572220131021.45.2 00.020.000.000.02  434343000.00 0.00
Copyright © Filipe Brandão