Old Results  Filipe Brandão's Homepage

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

Results for Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression)
23,153 benchmark instances solved in 9 days (less than 35 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

Donwload Results   Download Instances

Arc-flow VPSolver

NameTypeDescription#Solved#Total
BPP FLKBPP1D Bin-Packing Problems from FALKENAUER (1996).160 160
CSP FLKCSP1D Bin-Packing Problems from FALKENAUER (1996) [demand x 10^6].160 160
FiberCSPInstances taken from a real application in a paper tube industry in Japan.39 39
CutgenCSPCUTGEN (Gau and Wascher, 1995).1800 1800
1D-barCSP 1D-bar relaxations of the two-dimensional bin packing test dataset of Lodi et al. (1999).500 500
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
2CBP2CBPTwo-Constraint Bin Packing instances of Spieksma/Caprara/Toth.330 400
20CBPVBP20-dimensional vector packing instances based on the 2CBP dataset of Spieksma/Caprara/Toth.33 40
0-1 CSP FLK0-1 CSP1D Bin-Packing Problems from FALKENAUER (1996) [demand x 10^6; with binary patterns].160 160
0-1 Fiber0-1 CSPInstances taken from a real application in a paper tube industry in Japan [with binary patterns].39 39
0-1 Cutgen0-1 CSPCUTGEN (Gau and Wascher, 1995) [with binary patterns].1800 1800
0-1 1D-bar0-1 CSP 1D-bar relaxations of the two-dimensional bin packing test dataset of Lodi et al. (1999) [with binary patterns].500 500
BPPCBPPCBPP w/ Conflicts Problems from Muritiba et al. (2010).800 800
BPPC_CS0-1 CSP FPCSP w/ binary patterns and forbidden patterns based on the BPPC dataset of Muritiba et al. (2010).800 800
Card BPP FLKBPP Card1D Bin-Packing Problems from FALKENAUER (1996) [with cardinality constraints].320 320
Card CSP FLKCSP Card1D Bin-Packing Problems from FALKENAUER (1996) [demand x 10^6; with cardinality constraints].320 320
Card FiberCSP CardInstances taken from a real application in a paper tube industry in Japan [with cardinality constraints].279 279
Card CutgenCSP CardCUTGEN (Gau and Wascher, 1995) [with cardinality constraints].7299 7299
Card 1D-barCSP Card 1D-bar relaxations of the two-dimensional bin packing test dataset of Lodi et al. (1999) [with cardinality constraints].1415 1415
Card SchollBPP Card1D Bin-Packing Problems from SCHOLL/KLEIN/JUERGENS (1997) [with cardinality constraints].3748 3748
Card Hard28BPP CardThe 28 VERY hard BPP instances of J. Schoenfield (with m from 140 to 200) [with cardinality constraints].56 56
Card SCH/WAEBPP Card1D Bin-Packing Problems from SCHWERIN/WAESCHER (1998) [with cardinality constraints].1000 1000
Card WAE/GAUBPP Card1D Bin-Packing Problems from WAESCHER/GAU (1996) [with cardinality constraints].131 131
Graph ColoringColoringSome graph coloring instances from OR-Library4 4
TimetablingTimetabling"hard timetabling" instances from OR-Library5 5

WAE/GAU

chart
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
WAE_GAU110,000.049.6133.516.416.256,255.17140,010.8333.2634.537.51164.292.82,057.75 2,229.55
WAE_GAU210,000.049.8119.619.819.796,186.8099,897.4033.7642.025.47112.702.2110.60 228.77
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
TEST_5 [log]10,000571142827.994,923.0051,709.0046.8051.831.4255.178221.30 277.88
TEST_22 [log]10,00033571514.002,212.0012,311.0075.3780.620.241.8800.85 2.97
TEST_54 [log]10,000561441414.008,055.00207,509.0016.7817.199.97297.7602,982.77 3,290.50
TEST_55a [log]10,000521421515.007,319.00193,914.0021.1618.018.27217.1703,035.02 3,260.46
TEST_55b [log]10,000642392019.998,363.00299,677.0013.0311.2718.92339.4601,563.46 1,921.84
TEST_58 [log]10,00038912020.004,529.0037,892.0048.4955.330.9334.00029.30 64.23
TEST_65 [log]10,00035601615.001,053.007,298.0085.8782.980.120.4800.64 1.23
TEST_68 [log]10,000461631212.008,287.00202,277.0011.529.9711.51236.530263.60 511.64
TEST_75 [log]10,000462281313.008,785.00189,850.0010.0611.6118.10213.010258.14 489.25
TEST_84 [log]10,00063921615.986,008.00127,754.0031.5632.493.78136.760987.72 1,128.26
TEST_95 [log]10,000631531616.008,010.00217,529.0015.9620.8310.75258.652515,162.87 15,432.27
TEST_97 [log]10,000421191211.997,518.00132,410.0022.4922.286.12180.640187.31 374.08
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
TEST_14 [log]10,00047962323.006,087.0064,509.0031.9847.682.1770.751113.45 86.37
TEST_30 [log]10,000551112727.005,064.0054,561.0043.7143.011.3752.16015.56 69.09
TEST_44 [log]10,000561641414.008,390.00209,790.0012.7025.0914.31255.250289.53 559.09
TEST_49 [log]10,000431411110.997,971.00147,524.0018.4328.528.99177.070221.58 407.64
TEST_82 [log]10,00048862423.983,422.0023,103.0062.0065.800.508.29012.87 21.67
Arc-flow Vector Packing Solver
Copyright © Filipe Brandão