New Results  Filipe Brandão's Homepage

Arc Flow Formulation (w/ graph compression) Results: Hard28

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)
nameWnmzlb_lplb_sp#v1#a1#v2#a2#v3#a3#v4#a4%v%an_bbt_ppt_lpt_ipttzffdbfda_ffda_bfdr_ffdr_bfd
hard281000.0181.4161.8 70.470.2570.19 973.936816.846525.3127919.6936.836416.3934.136410.995.998.9 79.320.402.79105.80108.98  70.471.271.20.80.80.01 0.01
nameWnmzlb_lplb_sp#v1#a1#v2#a2#v3#a3#v4#a4%v%an_bbt_ppt_lpt_ipttzffdbfda_ffda_bfdr_ffdr_bfd
BPP_131000180161 6767.0066.96 9603898948560134189941389609413896098.099.9 120.433.077.9411.44  676868110.01 0.01
BPP_141000160136 6261.0060.96 9753053138292105165947303599443035396.899.4 2790.322.744.347.40  626262000.00 0.00
BPP_401000160144 5959.0058.98 9633968847892133546920392859173927995.299.0 750.432.7311.5014.66  596060110.02 0.02
BPP_471000180158 7171.0070.89 9703806746293128713940380229403802296.999.9 00.412.4917.0819.98  717272110.01 0.01
BPP_601000160144 6363.0062.94 884276813649098893759256117442558184.292.4 970.291.583.415.28  636464110.02 0.02
BPP_1191000200173 7776.0075.98 9674015552361142943930396449283964096.098.7 00.443.414.888.73  777777000.00 0.00
BPP_1441000200173 7373.0073.00 9854013652857143880949400269454001895.999.7 5050.463.4819.2523.19  737474110.01 0.01
BPP_1751000200185 8483.0082.92 9803880449515135874953387369513873297.099.8 1950.422.3538.1340.90  848484000.00 0.00
BPP_1781000200178 8080.0079.93 9923999351129140267964399479643994797.299.9 240.443.089.2512.77  808181110.01 0.01
BPP_1811000180157 7272.0071.94 9723382342462116803937336939343368796.199.6 00.363.163.066.58  727373110.01 0.01
BPP_1951000180161 6464.0063.99 9914130350972141265980412889804128898.9100.0 5640.463.182053.182056.82  646565110.02 0.02
BPP_3591000180164 7675.0074.85 9433054740088108837888303858843037793.799.4 190.332.072.795.19  767676000.00 0.00
BPP_3601000160148 6262.0061.92 9713506842869118864923335649213356094.995.7 00.372.318.3511.03  626363110.02 0.02
BPP_4191000200189 8080.0079.96 9854235353665147713958423049574230297.299.9 00.452.726.299.46  808181110.01 0.01
BPP_4851000180163 7171.0070.95 9973846648079132630990384569903845699.3100.0 400.412.497.069.96  717272110.01 0.01
BPP_5311000200175 8383.0082.84 9873545044451122378955353809543537896.799.8 00.372.315.097.77  838484110.01 0.01
BPP_5611000200177 7272.0071.99 9904365156390154451951435809514358096.199.8 320.533.57204.36208.46  727373110.01 0.01
BPP_6401000180165 7474.0073.90 9693571145634125041926349799183496394.797.9 00.392.3222.9025.61  747575110.01 0.01
BPP_6451000160141 5858.0057.99 9973677643929122640984367559843675598.799.9 810.423.34111.79115.55  585959110.02 0.02
BPP_7091000180160 6767.0066.99 9663339243341118142916332409123323294.499.5 770.362.504.267.12  676868110.01 0.01
BPP_7161000180158 7675.0074.84 9842988237463102840950291829482917896.397.6 50.321.6110.4312.36  767676000.00 0.00
BPP_7421000160148 6464.0063.94 9683286341001112929907309439003092993.094.1 00.342.009.7412.08  646565110.02 0.02
BPP_7661000160143 6262.0061.96 9583068738960106691901304728943045893.399.3 40.322.453.406.17  626363110.02 0.02
BPP_7811000200174 7171.0071.00 9974679458114161028981461079804610598.398.5 200.525.02191.24196.78  717272110.01 0.01
BPP_7851000180163 6867.9967.98 9713753147128129845943374829403747696.899.9 00.413.0644.1747.64  686969110.01 0.01
BPP_8141000200179 8181.0080.82 9984248553693147875966424279664242796.899.9 00.452.947.1210.51  818282110.01 0.01
BPP_8321000160139 6060.0059.98 952279113683599677889272018892720193.497.5 1250.322.7252.3055.34  606161110.02 0.02
BPP_9001000200173 7575.0074.98 9974213254246148630983416289804162298.398.8 670.473.3398.98102.78  757676110.01 0.01
Copyright © Filipe Brandão