Old Results  Filipe Brandão's Homepage

Arc-flow Formulation (w/ graph compression) Results: Card 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

Card WAE/GAU

chart
NAMEWCMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
WAE_GAU110,000.06.651.1159.031.931.577,295.97113,440.5490.1488.7914.06156.890.1902.73 1,073.69
WAE_GAU210,000.06.049.5134.830.430.085,515.5976,173.2692.0792.3812.4186.722.6689.01 788.15
NAMEWCMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
TEST_5.C2 [log]10,0002571145757.004.00116.0099.7496.380.020.0000.00 0.02
TEST_5.C3 [log]10,0003571143838.0063.00548.0099.2998.340.160.0100.03 0.19
TEST_5.C4 [log]10,0004571142928.50336.003,002.0098.0497.410.620.0800.39 1.09
TEST_5.C5 [log]10,0005571142827.99891.008,662.0096.5495.591.300.5002.08 3.88
TEST_22.C2 [log]10,000233572928.504.0068.0099.2994.050.010.0000.00 0.01
TEST_22.C3 [log]10,000333571919.0036.00207.0099.1697.900.040.0000.01 0.06
TEST_22.C4 [log]10,000433571514.25120.00761.0098.9698.080.110.0200.06 0.19
TEST_54.C2 [log]10,0002561447272.004.00113.0099.7196.220.020.0000.00 0.02
TEST_54.C3 [log]10,0003561444848.0022.00220.0099.6899.360.150.0000.01 0.16
TEST_54.C4 [log]10,0004561443636.0057.00377.0099.6399.771.130.0000.01 1.14
TEST_54.C5 [log]10,0005561442928.80259.001,891.0098.9499.484.010.0400.19 4.25
TEST_54.C6 [log]10,0006561442424.001,743.0018,385.0094.8496.598.370.9802.66 12.01
TEST_54.C7 [log]10,0007561442120.574,962.0071,052.0088.4889.6612.9112.97062.92 88.81
TEST_54.C8 [log]10,0008561441818.008,466.00139,318.0083.8282.8717.4760.460211.63 289.56
TEST_54.C9 [log]10,0009561441616.0012,200.00211,416.0080.1677.1321.51141.690913.43 1,076.63
TEST_54.C10 [log]10,00010561441514.4016,763.00284,489.0076.2672.1329.05353.050485.30 867.40
TEST_54.C11 [log]10,00011561441414.0021,353.00355,106.0073.2067.8833.57530.7001,708.02 2,272.29
TEST_55a.C2 [log]10,0002521427171.004.00105.0099.6695.970.020.0000.00 0.02
TEST_55a.C3 [log]10,0003521424847.3317.00192.0099.7199.330.160.0000.01 0.16
TEST_55a.C4 [log]10,0004521423635.5064.00381.0099.5199.711.170.0000.02 1.18
TEST_55a.C5 [log]10,0005521422928.40176.00881.0099.2099.714.100.0200.03 4.15
TEST_55a.C6 [log]10,0006521422423.671,186.0012,580.0096.1697.308.520.5203.55 12.58
TEST_55a.C7 [log]10,0007521422120.293,993.0058,536.0089.9190.1913.0612.33063.69 89.08
TEST_55a.C8 [log]10,0008521421817.757,710.00126,764.0083.9982.0414.5645.030311.17 370.76
TEST_55a.C9 [log]10,0009521421615.7811,356.00198,604.0079.9475.0820.73134.590658.59 813.91
TEST_55a.C10 [log]10,00010521421515.0014,750.00267,473.0077.2669.4124.58379.530891.68 1,295.79
TEST_55b.C2 [log]10,000264239120119.504.00130.0099.7596.510.020.0000.00 0.02
TEST_55b.C3 [log]10,0003642398079.6721.00242.0099.7099.470.240.0000.01 0.25
TEST_55b.C4 [log]10,0004642396059.7556.00407.0099.6399.812.430.0000.02 2.45
TEST_55b.C5 [log]10,0005642394847.80217.001,302.0099.1099.738.130.0200.06 8.20
TEST_55b.C6 [log]10,0006642394039.831,413.0016,844.0095.7797.7017.070.8102.06 19.94
TEST_55b.C7 [log]10,0007642393534.144,528.0077,052.0089.3691.9026.5113.25056.80 96.56
TEST_55b.C8 [log]10,0008642393029.888,691.00174,114.0083.1984.7036.2272.990364.04 473.25
TEST_55b.C9 [log]10,0009642392726.5613,348.00290,283.0078.0477.6350.00214.4201,511.84 1,776.26
TEST_55b.C10 [log]10,00010642392423.9017,518.00411,004.0074.9171.3853.96365.0902,782.78 3,201.83
TEST_55b.C11 [log]10,00011642392221.7322,147.00527,936.0071.9166.0960.60721.3204,839.01 5,620.93
TEST_55b.C12 [log]10,00012642392019.9926,433.00631,154.0069.9062.0867.211,169.5302,777.91 4,014.65
TEST_58.C2 [log]10,000238914645.504.0077.0099.4794.930.010.0000.00 0.01
TEST_58.C3 [log]10,000338913130.3341.00263.0099.3398.260.040.0000.02 0.06
TEST_58.C4 [log]10,000438912322.75158.001,071.0098.8798.320.190.0200.12 0.33
TEST_58.C5 [log]10,000538912020.00435.003,255.0098.0397.510.540.1381.35 2.02
TEST_65.C2 [log]10,000235603030.004.0071.0099.3694.410.010.0000.00 0.01
TEST_65.C3 [log]10,000335602020.0039.00250.0099.1097.650.030.0000.01 0.04
TEST_65.C4 [log]10,000435601615.00150.001,087.0098.5496.980.060.0200.04 0.12
TEST_68.C2 [log]10,0002461638281.504.0093.0099.6095.580.010.0000.00 0.01
TEST_68.C3 [log]10,0003461635554.3318.00178.0099.6899.200.090.0000.01 0.09
TEST_68.C4 [log]10,0004461634140.7544.00299.0099.6699.740.680.0000.01 0.69
TEST_68.C5 [log]10,0005461633332.60131.00662.0099.4199.762.880.0100.02 2.91
TEST_68.C6 [log]10,0006461632827.17665.005,697.0097.8698.766.560.1300.41 7.10
TEST_68.C7 [log]10,0007461632423.292,581.0028,389.0093.5595.3911.022.4208.43 21.87
TEST_68.C8 [log]10,0008461632120.386,181.0079,277.0087.3289.4315.6020.84090.93 127.36
TEST_68.C9 [log]10,0009461631918.1110,181.00148,884.0082.2582.7920.0951.050262.67 333.80
TEST_68.C10 [log]10,00010461631716.3014,142.00226,157.0078.5176.5626.16178.170906.43 1,110.76
TEST_68.C11 [log]10,00011461631514.8217,790.00301,166.0075.9971.3831.52311.8501,791.88 2,135.25
TEST_68.C12 [log]10,00012461631413.5821,504.00371,400.0073.8467.1132.69517.8301,845.08 2,395.59
TEST_68.C13 [log]10,00013461631312.5425,710.00435,396.0071.4763.6435.05666.890993.24 1,695.19
TEST_68.C14 [log]10,00014461631212.0029,268.00485,808.0070.0961.3836.84844.82024,985.11 25,866.77
TEST_75.C2 [log]10,000246228114114.004.0093.0099.5995.550.010.0000.00 0.01
TEST_75.C3 [log]10,0003462287676.009.00151.0099.8599.320.080.0000.00 0.08
TEST_75.C4 [log]10,0004462285757.0035.00271.0099.7599.760.530.0000.01 0.54
TEST_75.C5 [log]10,0005462284645.60135.00699.0099.4299.752.200.0100.02 2.23
TEST_75.C6 [log]10,0006462283838.00748.006,394.0097.7398.565.420.1500.57 6.14
TEST_75.C7 [log]10,0007462283332.573,128.0032,013.0092.6394.609.482.3007.52 19.29
TEST_75.C8 [log]10,0008462282928.507,212.0082,734.0086.1188.5413.8517.85050.44 82.14
TEST_75.C9 [log]10,0009462282625.3311,460.00142,265.0081.3383.0618.6667.180245.24 331.08
TEST_75.C10 [log]10,00010462282322.8014,735.00193,532.0079.1879.6423.45112.510499.19 635.15
TEST_75.C11 [log]10,00011462282120.7317,008.00234,636.0078.7877.7628.44205.840799.21 1,033.49
TEST_75.C12 [log]10,00012462281919.0019,675.00276,654.0078.0276.0133.92381.0101,525.37 1,940.30
TEST_75.C13 [log]10,00013462281817.5424,011.00327,209.0075.7073.7138.46520.570703.96 1,262.99
TEST_75.C14 [log]10,00014462281716.2929,338.00384,394.0072.8671.1044.67670.770962.82 1,678.27
TEST_75.C15 [log]10,00015462281615.2033,864.00440,205.0071.1468.7949.30865.3001,105.41 2,020.01
TEST_75.C16 [log]10,00016462281514.2537,942.00492,156.0070.0266.8754.25975.3801,753.11 2,782.74
TEST_75.C17 [log]10,00017462281413.4142,903.00542,967.0068.3965.1159.151,521.9102,168.60 3,749.66
TEST_75.C18 [log]10,00018462281313.0047,058.00589,734.0067.5263.6865.762,318.34024,545.91 26,930.01
TEST_84.C2 [log]10,000263924646.004.00127.0099.7796.660.020.0000.00 0.02
TEST_84.C3 [log]10,000363923130.6763.00366.0099.3699.240.190.0000.02 0.21
TEST_84.C4 [log]10,000463922323.00285.003,328.0098.4498.451.220.0600.16 1.44
TEST_84.C5 [log]10,000563921918.401,119.0015,283.0095.7895.713.080.4802.87 6.43
TEST_84.C6 [log]10,000663921615.983,373.0050,723.0090.2389.195.114.37026.37 35.86
TEST_95.C2 [log]10,0002631537776.504.00127.0099.7696.570.020.0000.00 0.02
TEST_95.C3 [log]10,0003631535151.0026.00253.0099.6699.440.170.0000.01 0.18
TEST_95.C4 [log]10,0004631533938.2557.00405.0099.6599.801.440.0000.01 1.45
TEST_95.C5 [log]10,0005631533130.60430.003,903.0098.3299.074.970.0800.29 5.34
TEST_95.C6 [log]10,0006631532625.502,277.0029,495.0093.4495.129.822.4709.67 21.95
TEST_95.C7 [log]10,0007631532221.866,088.0093,839.0086.0687.7014.9918.430108.64 142.06
TEST_95.C8 [log]10,0008631532019.129,965.00160,264.0081.0282.2619.9649.910350.18 420.06
TEST_95.C9 [log]10,0009631531717.0012,728.00213,347.0079.1979.3124.53140.630704.38 869.54
TEST_95.C10 [log]10,00010631531616.0014,968.00258,699.0078.5077.4828.88269.3101,640.50 1,938.69
TEST_97.C2 [log]10,0002421196059.504.0086.0099.5495.210.010.0000.00 0.01
TEST_97.C3 [log]10,0003421194039.6720.00173.0099.6599.080.060.0000.01 0.07
TEST_97.C4 [log]10,0004421193029.7558.00325.0099.5999.680.450.0000.01 0.46
TEST_97.C5 [log]10,0005421192423.80235.001,399.0098.9799.421.770.0200.06 1.85
TEST_97.C6 [log]10,0006421192019.831,071.009,569.0096.6497.403.800.3901.40 5.59
TEST_97.C7 [log]10,0007421191717.003,535.0037,257.0091.3492.146.084.31021.08 31.46
TEST_97.C8 [log]10,0008421191514.886,922.0081,598.0086.0885.528.2520.66075.46 104.37
TEST_97.C9 [log]10,0009421191413.2210,558.00132,127.0082.0179.3410.1859.960332.27 402.40
TEST_97.C10 [log]10,00010421191211.9914,689.00183,737.0078.2773.9211.86163.8701,388.64 1,564.38
NAMEWCMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
TEST_14.C2 [log]10,000247964848.004.0096.0099.6395.710.010.0000.00 0.01
TEST_14.C3 [log]10,000347963232.0039.00325.0099.5198.620.080.0000.01 0.09
TEST_14.C4 [log]10,000447962424.00208.001,532.0098.7498.510.350.0300.14 0.53
TEST_14.C5 [log]10,000547962323.00557.004,792.0097.7797.660.940.21480.75 1.90
TEST_30.C2 [log]10,0002551115655.504.00111.0099.7396.350.010.0000.00 0.01
TEST_30.C3 [log]10,0003551113737.0058.00550.0099.3098.150.100.0100.01 0.12
TEST_30.C4 [log]10,0004551112827.75285.002,382.0098.2597.650.320.0500.18 0.55
TEST_30.C5 [log]10,0005551112727.00765.007,290.0096.8895.800.730.28403.28 4.30
TEST_44.C2 [log]10,0002561648282.004.00113.0099.7196.260.020.0000.00 0.02
TEST_44.C3 [log]10,0003561645554.6720.00213.0099.7299.400.140.0000.01 0.15
TEST_44.C4 [log]10,0004561644141.0044.00336.0099.7299.821.180.0000.01 1.20
TEST_44.C5 [log]10,0005561643332.80227.001,471.0099.1099.655.180.0200.07 5.27
TEST_44.C6 [log]10,0006561642827.331,395.0012,521.0095.9698.0612.010.5401.98 14.52
TEST_44.C7 [log]10,0007561642423.434,189.0052,674.0090.4393.7820.207.90024.17 52.28
TEST_44.C8 [log]10,0008561642120.508,005.00115,738.0084.8788.7428.9048.170196.61 273.69
TEST_44.C9 [log]10,0009561641918.2212,193.00190,443.0080.3184.0137.54140.310596.08 773.93
TEST_44.C10 [log]10,00010561641716.4016,526.00270,824.0076.6479.7745.42264.1601,110.69 1,420.28
TEST_44.C11 [log]10,00011561641514.9121,336.00349,537.0073.1576.2652.58428.540651.38 1,132.50
TEST_44.C12 [log]10,00012561641414.0025,804.00423,376.0070.6773.4658.59675.13018,496.70 19,230.42
TEST_49.C2 [log]10,0002431417170.504.0087.0099.5495.290.010.0000.00 0.01
TEST_49.C3 [log]10,0003431414747.0010.00145.0099.8299.230.060.0000.00 0.07
TEST_49.C4 [log]10,0004431413635.2533.00253.0099.7599.740.410.0000.01 0.42
TEST_49.C5 [log]10,0005431412928.20101.00536.0099.5599.781.870.0100.02 1.90
TEST_49.C6 [log]10,0006431412423.50504.003,596.0098.4399.144.850.0800.42 5.35
TEST_49.C7 [log]10,0007431412120.142,038.0017,745.0095.1196.908.921.1203.39 13.43
TEST_49.C8 [log]10,0008431411817.625,547.0053,782.0089.1492.4313.5310.80042.73 67.06
TEST_49.C9 [log]10,0009431411615.679,385.00101,625.0084.4787.8717.9743.790144.03 205.79
TEST_49.C10 [log]10,00010431411514.1012,885.00153,408.0081.5183.9221.98119.720414.51 556.21
TEST_49.C11 [log]10,00011431411312.8217,342.00212,587.0078.0179.9425.96251.990269.61 547.55
TEST_49.C12 [log]10,00012431411211.7521,995.00275,147.0075.0076.2029.42343.870407.27 780.56
TEST_49.C13 [log]10,00013431411110.9925,777.00334,881.0073.4273.0932.56611.6901,062.04 1,706.29
TEST_82.C2 [log]10,000248864343.0013.00102.0098.6494.790.010.0000.00 0.01
TEST_82.C3 [log]10,000348862928.6750.00398.0099.1697.410.040.0000.02 0.06
TEST_82.C4 [log]10,000448862423.99183.001,275.0098.6397.610.110.0200.34 0.47
Arc-flow Vector Packing Solver
Copyright © Filipe Brandão