New Results  Filipe Brandão's Homepage

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

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
WAE_GAU110000.0133.549.6 16.416.2516.24 9183.6183103.8202504.2569744.97970.2170253.67930.4170172.986.492.9 12.252.19189.045278.095469.32  16.417.217.20.80.80.05 0.05
WAE_GAU210000.0119.649.8 19.819.7919.79 9266.4154607.6165749.8467574.48197.4146509.08173.6146461.088.294.7 11.801.83181.798807.838991.44  19.820.820.81.01.00.06 0.06
nameWnmzlb_lplb_sp#v1#a1#v2#a2#v3#a3#v4#a4%v%an_bbt_ppt_lpt_ipttzffdbfda_ffda_bfdr_ffdr_bfd
TEST_51000011457 2827.9927.99 925310735211900632685868448045668288042073.874.9 401.13114.613581.903697.64  282929110.04 0.04
TEST_22100005733 1514.0014.00 8982635246446617449275565962074805946783.393.6 00.6846.756.6154.04  151515000.00 0.00
TEST_541000014456 1414.0014.00 96792505862800777913828891240427882724029891.295.9 13.06292.695378.555674.30  141515110.07 0.07
TEST_55a1000014252 1515.0015.00 92832365012665347510038331227264832622725489.796.1 812.98286.5327634.2227923.73  151616110.07 0.07
TEST_55b1000023964 2019.9919.99 961633772937137010612378956330819892233074792.897.9 244.28359.9620572.6220936.86  202121110.05 0.05
TEST_58100009138 2020.0020.00 8793848358826724378371927223971377212781.285.0 00.89101.091013.631115.61  202121110.05 0.05
TEST_65100006035 1615.0015.00 7454428904662112122450653471150113460367.280.7 10.4229.164.0733.65  161616000.00 0.00
TEST_681000016346 1212.0012.00 93662246722427236913868541209686849520959490.793.3 02.61210.36224.55437.52  121313110.08 0.08
TEST_751000022846 1313.0013.00 97682147952326146604879217200749920120071794.293.4 02.61223.163294.243520.01  131414110.08 0.08
TEST_84100009263 1615.9815.98 87791892382225096166987249163875717316372181.786.5 02.25142.431105.011249.69  161717110.06 0.06
TEST_951000015363 1616.0016.00 95312747503098068753008973262927894026286193.895.7 03.34291.37379.07673.78  161717110.06 0.06
TEST_971000011942 1211.9911.99 96991703731860575230898827160270882516026691.094.1 01.96170.38142.62314.96  121313110.08 0.08
nameWnmzlb_lplb_sp#v1#a1#v2#a2#v3#a3#v4#a4%v%an_bbt_ppt_lpt_ipttzffdbfda_ffda_bfdr_ffdr_bfd
TEST_14100009647 2323.0023.00 89491233051316223686517806107085776110699586.786.8 01.35105.8341.20148.38  232424110.04 0.04
TEST_301000011155 2727.0027.00 89969573310653529081175978802975658796384.191.9 01.05140.649.84151.53  272828110.04 0.04
TEST_441000016456 1414.0014.00 96102800643017698643829119274278910627425294.897.9 03.50318.847300.287622.62  141515110.07 0.07
TEST_491000014143 1110.9910.99 97722063772194446257219391204086938120406696.098.9 592.51276.1836629.7536908.44  111212110.09 0.09
TEST_82100008648 2423.9823.97 9005675596937918830770745906770555902978.387.4 00.7367.4658.06126.25  242525110.04 0.04
Copyright © Filipe Brandão