Old Results  Filipe Brandão's Homepage

Arc-flow Formulation (w/ graph compression) Results: BPP FLK

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

BPP FLK

chart
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
binpack1150.063.2120.049.048.5096.551,875.3524.5418.810.030.030.00.11 0.17
binpack2150.077.2250.0101.6101.09108.202,701.4017.9212.940.040.061.20.24 0.33
binpack3150.080.8500.0201.2200.64111.902,948.2015.8311.600.050.066.00.38 0.49
binpack4150.081.01,000.0400.6400.01112.002,956.1015.7911.710.050.060.00.26 0.37
binpack51,000.050.060.020.020.0054.05665.6590.1287.330.020.010.00.04 0.06
binpack61,000.086.2120.040.040.0094.951,930.1583.8881.760.050.030.00.19 0.26
binpack71,000.0140.1249.083.083.00150.205,554.7076.6571.140.100.114.40.86 1.07
binpack81,000.0194.2501.0167.0167.00202.2011,800.0071.0060.510.200.290.01.78 2.27
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
u120_00 [log]150581204847.2795.001,623.0025.7824.020.030.0300.07 0.13
u120_01 [log]150591204948.0596.001,795.0025.0017.320.020.0300.07 0.12
u120_02 [log]150611204645.29103.001,972.0021.9721.340.030.0400.14 0.20
u120_03 [log]150681204948.63100.002,040.0023.0820.280.030.0300.09 0.15
u120_04 [log]150621205049.0999.001,837.0022.6615.970.020.0300.10 0.15
u120_05 [log]150611204847.4998.001,854.0023.4416.450.030.0300.11 0.17
u120_06 [log]150651204847.58101.002,035.0022.3117.840.030.0400.16 0.23
u120_07 [log]150641204948.6692.001,760.0025.8119.230.030.0300.13 0.18
u120_08 [log]150671205049.91101.002,104.0022.3117.390.030.0300.13 0.20
u120_09 [log]150641204645.80104.002,141.0020.0014.430.040.0500.15 0.24
u120_10 [log]150641205251.2892.001,731.0027.5621.100.030.0400.07 0.14
u120_11 [log]150601204948.3991.001,621.0028.3520.580.030.0300.08 0.14
u120_12 [log]150631204847.8799.002,023.0022.6618.430.030.0400.14 0.21
u120_13 [log]150621204948.0198.001,889.0023.4416.270.030.0400.14 0.21
u120_14 [log]150611205049.1793.001,681.0025.6020.970.030.0300.09 0.15
u120_15 [log]150631204847.3896.001,896.0025.5817.310.030.0400.12 0.19
u120_16 [log]150641205251.3390.001,707.0027.4219.290.020.0300.08 0.13
u120_17 [log]150641205251.5088.001,670.0029.0320.890.020.0200.07 0.12
u120_18 [log]150661204948.3894.001,979.0025.9817.990.030.0300.08 0.14
u120_19 [log]150681204948.86101.002,149.0022.9019.120.040.0400.14 0.22
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
u250_00 [log]150712509998.55104.002,304.0020.0012.990.030.0500.21 0.29
u250_01 [log]1507825010099.03110.002,730.0017.2915.190.040.0600.22 0.32
u250_02 [log]15076250102101.42108.002,738.0017.5610.260.060.0500.23 0.34
u250_03 [log]1507925010099.43109.002,830.0017.4211.780.050.0600.31 0.42
u250_04 [log]15076250101100.61110.002,706.0016.6710.010.040.0500.23 0.32
u250_05 [log]15078250101100.83108.002,679.0018.1814.110.040.0600.26 0.36
u250_06 [log]15078250102101.03112.002,869.0015.7911.510.040.0600.21 0.31
u250_07 [log]15077250103102.89107.002,634.0018.3213.530.040.0600.19 0.29
u250_08 [log]15078250105104.92105.002,662.0019.8514.430.040.0500.11 0.20
u250_09 [log]15080250101100.20109.002,801.0017.4213.120.040.0500.14 0.23
u250_10 [log]15077250105104.39107.002,640.0018.3213.730.040.0500.21 0.29
u250_11 [log]15080250101100.71109.002,821.0017.4212.800.040.0800.24 0.36
u250_12 [log]15076250105104.98102.002,530.0020.9313.030.040.07240.80 0.90
u250_13 [log]15075250103102.04109.002,662.0017.4211.880.040.0400.11 0.19
u250_14 [log]1507925010099.17112.002,839.0015.7911.860.040.0600.20 0.30
u250_15 [log]15078250105104.86105.002,699.0019.8512.480.040.0500.14 0.23
u250_16 [log]150762509796.51112.002,743.0015.7912.810.050.0600.29 0.39
u250_17 [log]1507625010099.17108.002,618.0018.1815.360.040.0600.20 0.30
u250_18 [log]1507625010099.70110.002,668.0017.2913.350.040.0700.23 0.34
u250_19 [log]15081250102101.36108.002,855.0018.8014.550.040.0600.21 0.31
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
u500_00 [log]15081500198197.58112.002,954.0015.7911.770.050.0600.32 0.43
u500_01 [log]15081500201200.85112.002,987.0015.7910.780.060.0700.19 0.31
u500_02 [log]15080500202201.44112.002,886.0015.7911.850.050.0600.25 0.36
u500_03 [log]15081500204203.81112.002,971.0015.7911.230.050.0700.32 0.44
u500_04 [log]15080500206205.11110.002,799.0016.6713.450.040.0500.27 0.36
u500_05 [log]15081500206205.09112.002,978.0015.7911.020.060.0900.27 0.42
u500_06 [log]15081500207206.91112.002,961.0015.7911.510.040.0500.21 0.30
u500_07 [log]15080500204203.98112.002,916.0015.7911.530.050.061212.99 3.10
u500_08 [log]15081500196195.68112.002,958.0015.7911.650.040.0600.23 0.34
u500_09 [log]15081500202201.06112.002,931.0015.7912.460.060.0800.38 0.52
u500_10 [log]15081500200199.07112.002,978.0015.7911.020.050.0600.16 0.28
u500_11 [log]15081500200199.43112.002,957.0015.7911.650.040.0600.24 0.35
u500_12 [log]15081500199198.62112.002,967.0015.7911.380.050.0600.26 0.38
u500_13 [log]15081500196195.59112.002,957.0015.7911.600.050.0600.29 0.40
u500_14 [log]15081500204203.03112.002,978.0015.7911.050.050.0600.14 0.24
u500_15 [log]15080500201200.13112.002,962.0015.7911.240.040.0700.22 0.33
u500_16 [log]15081500202201.01112.002,954.0015.7911.720.050.0600.20 0.31
u500_17 [log]15081500198197.43112.002,973.0015.7911.200.040.0600.24 0.35
u500_18 [log]15081500202201.29112.002,948.0015.7911.950.040.0600.15 0.26
u500_19 [log]15081500196195.63112.002,949.0015.7911.890.040.0600.25 0.35
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
u1000_00 [log]150811,000399398.43112.002,956.0015.7911.710.060.0600.29 0.41
u1000_01 [log]150811,000406405.25112.002,957.0015.7911.680.050.0600.21 0.32
u1000_02 [log]150811,000411410.20112.002,956.0015.7911.710.050.0700.19 0.31
u1000_03 [log]150811,000411410.87112.002,956.0015.7911.710.040.0700.32 0.43
u1000_04 [log]150811,000397396.74112.002,956.0015.7911.710.040.0600.28 0.38
u1000_05 [log]150811,000399398.49112.002,956.0015.7911.710.040.0600.37 0.47
u1000_06 [log]150811,000395394.21112.002,956.0015.7911.710.040.0600.25 0.35
u1000_07 [log]150811,000404403.16112.002,956.0015.7911.710.040.0600.33 0.43
u1000_08 [log]150811,000399398.43112.002,956.0015.7911.710.060.0700.22 0.35
u1000_09 [log]150811,000397396.93112.002,956.0015.7911.710.050.0600.29 0.40
u1000_10 [log]150811,000400399.34112.002,956.0015.7911.710.050.0600.31 0.43
u1000_11 [log]150811,000401400.52112.002,957.0015.7911.680.050.0600.27 0.38
u1000_12 [log]150811,000393392.24112.002,956.0015.7911.710.060.0700.22 0.35
u1000_13 [log]150811,000396395.27112.002,956.0015.7911.710.040.0600.28 0.39
u1000_14 [log]150811,000394393.89112.002,956.0015.7911.710.050.0700.25 0.37
u1000_15 [log]150811,000402401.81112.002,956.0015.7911.710.040.0700.20 0.31
u1000_16 [log]150811,000404403.03112.002,956.0015.7911.710.040.0700.18 0.29
u1000_17 [log]150811,000404403.80112.002,956.0015.7911.710.040.0700.27 0.39
u1000_18 [log]150811,000399398.19112.002,956.0015.7911.710.050.0600.19 0.30
u1000_19 [log]150811,000400399.33112.002,956.0015.7911.710.040.0700.25 0.36
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
t60_00 [log]1,00050602020.0055.00644.0089.9587.950.030.0100.03 0.06
t60_01 [log]1,00056602020.0056.00734.0089.9188.470.020.0100.05 0.08
t60_02 [log]1,00048602020.0052.00601.0090.5388.510.020.0100.03 0.06
t60_03 [log]1,00049602020.0056.00678.0089.6386.310.020.0100.08 0.11
t60_04 [log]1,00048602020.0049.00661.0090.9385.970.020.0100.04 0.06
t60_05 [log]1,00050602020.0053.00665.0090.2987.230.020.0100.02 0.05
t60_06 [log]1,00051602020.0053.00696.0090.3186.520.020.0100.05 0.08
t60_07 [log]1,00050602020.0055.00667.0089.9587.240.020.0100.03 0.06
t60_08 [log]1,00049602020.0052.00639.0090.4687.080.020.0100.02 0.05
t60_09 [log]1,00049602020.0055.00649.0089.9386.680.020.0100.03 0.06
t60_10 [log]1,00053602020.0057.00747.0089.6986.430.020.0100.03 0.07
t60_11 [log]1,00046602020.0052.00612.0090.3786.100.010.0100.02 0.04
t60_12 [log]1,00053602020.0057.00720.0089.7387.400.020.0100.05 0.08
t60_13 [log]1,00051602020.0054.00709.0090.2087.500.020.0100.04 0.07
t60_14 [log]1,00050602020.0056.00647.0089.8688.340.020.0100.02 0.05
t60_15 [log]1,00051602020.0056.00660.0089.8489.000.020.0100.06 0.09
t60_16 [log]1,00046602020.0047.00598.0091.2887.440.020.0100.03 0.05
t60_17 [log]1,00048602020.0054.00639.0089.9487.450.020.0100.03 0.06
t60_18 [log]1,00050602020.0056.00707.0089.8286.140.020.0100.03 0.05
t60_19 [log]1,00051602020.0056.00640.0089.8788.760.020.0100.02 0.05
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
t120_00 [log]1,000861204040.0096.001,879.0083.7082.550.040.0300.14 0.21
t120_01 [log]1,000851204040.0093.001,942.0084.1880.080.050.0300.20 0.29
t120_02 [log]1,000911204040.00101.002,076.0083.0082.230.060.0400.27 0.38
t120_03 [log]1,000861204040.0095.001,856.0083.8782.790.050.0300.12 0.20
t120_04 [log]1,000921204040.0099.002,170.0083.3681.950.040.0300.21 0.28
t120_05 [log]1,000881204040.0095.001,961.0083.9382.480.050.0300.19 0.27
t120_06 [log]1,000861204040.0092.001,908.0084.3881.460.050.0300.20 0.28
t120_07 [log]1,000871204040.0095.002,013.0083.9080.670.050.0300.09 0.17
t120_08 [log]1,000861204040.0097.001,965.0083.5380.960.050.0300.25 0.32
t120_09 [log]1,000851204040.0093.001,857.0084.1881.370.040.0300.08 0.15
t120_10 [log]1,000831204040.0092.001,773.0084.3082.590.050.0300.26 0.34
t120_11 [log]1,000861204040.0093.001,843.0084.1882.840.040.0300.19 0.26
t120_12 [log]1,000821204040.0091.001,857.0084.4480.860.030.0200.25 0.30
t120_13 [log]1,000871204040.0094.001,943.0084.0481.460.050.0300.16 0.24
t120_14 [log]1,000831204040.0094.001,715.0083.9683.460.050.0200.21 0.28
t120_15 [log]1,000811204040.0092.001,656.0084.2583.780.030.0200.16 0.21
t120_16 [log]1,000871204040.00100.002,009.0083.0580.870.040.0300.23 0.30
t120_17 [log]1,000901204040.0098.002,137.0083.4581.450.040.0300.18 0.25
t120_18 [log]1,000851204040.0091.001,950.0084.5281.140.040.0300.11 0.18
t120_19 [log]1,000871204040.0098.002,093.0083.3980.200.060.0300.21 0.30
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
t249_00 [log]1,0001342498383.00139.005,085.0078.1872.280.100.1000.58 0.77
t249_01 [log]1,0001402498383.00153.005,564.0076.2170.810.090.1000.60 0.79
t249_02 [log]1,0001392498383.00147.005,316.0077.1072.180.100.1200.83 1.05
t249_03 [log]1,0001422498383.00152.005,906.0076.4369.380.100.1101.01 1.22
t249_04 [log]1,0001342498383.00146.005,098.0077.0872.290.090.0800.56 0.73
t249_05 [log]1,0001452498383.00154.005,880.0076.2370.570.100.1100.35 0.57
t249_06 [log]1,0001382498383.00149.005,629.0076.7669.460.090.1000.71 0.90
t249_07 [log]1,0001372498383.00141.005,411.0077.9770.510.100.1100.66 0.87
t249_08 [log]1,0001392498383.00145.005,413.0077.4171.400.100.1100.31 0.52
t249_09 [log]1,0001412498383.00148.005,600.0077.0270.680.100.1000.41 0.60
t249_10 [log]1,0001402498383.00153.005,605.0076.2171.310.110.1000.52 0.74
t249_11 [log]1,0001412498383.00154.005,679.0076.0570.730.100.1400.87 1.12
t249_12 [log]1,0001412498383.00156.005,544.0075.7871.120.100.0900.81 1.00
t249_13 [log]1,0001412498383.00149.005,739.0076.8670.010.100.1000.34 0.54
t249_14 [log]1,0001452498383.00159.005,665.0075.4672.220.100.12885.62 5.84
t249_15 [log]1,0001422498383.00154.005,533.0076.1272.570.140.1100.79 1.04
t249_16 [log]1,0001442498383.00151.005,858.0076.6671.170.120.1400.74 0.99
t249_17 [log]1,0001452498383.00159.005,812.0075.4670.880.120.1500.93 1.20
t249_18 [log]1,0001382498383.00149.005,312.0076.7671.910.100.1200.29 0.51
t249_19 [log]1,0001362498383.00146.005,445.0077.1571.330.090.0800.28 0.45
NAMEWMNZIPZLPVFAFRVRATPRETLPNNTIPTTOT
t501_00 [log]1,000190501167167.00199.0011,515.0071.2859.850.190.2902.75 3.23
t501_01 [log]1,000192501167167.00201.0011,451.0071.0861.300.230.2902.44 2.96
t501_02 [log]1,000190501167167.00197.0010,861.0071.5762.850.220.3201.72 2.26
t501_03 [log]1,000199501167167.00207.0012,122.0070.5161.050.200.2801.63 2.11
t501_04 [log]1,000195501167167.00202.0011,815.0071.0660.650.200.2602.56 3.02
t501_05 [log]1,000195501167167.00200.0011,882.0071.3560.480.180.2901.74 2.22
t501_06 [log]1,000196501167167.00206.0012,032.0070.5360.010.190.3001.15 1.65
t501_07 [log]1,000192501167167.00198.0011,493.0071.5160.880.240.2701.84 2.35
t501_08 [log]1,000196501167167.00208.0012,137.0070.2460.050.200.2701.62 2.09
t501_09 [log]1,000189501167167.00196.0011,032.0071.6861.710.190.2901.62 2.10
t501_10 [log]1,000190501167167.00196.0011,266.0071.7261.000.190.3101.51 2.02
t501_11 [log]1,000195501167167.00205.0011,996.0070.6359.770.190.2801.73 2.20
t501_12 [log]1,000189501167167.00193.0011,204.0072.1160.930.190.2802.38 2.85
t501_13 [log]1,000198501167167.00205.0012,362.0070.7659.610.210.2901.09 1.58
t501_14 [log]1,000203501167167.00212.0012,867.0069.9759.700.240.3601.57 2.17
t501_15 [log]1,000197501167167.00207.0012,013.0070.4360.680.200.3302.09 2.63
t501_16 [log]1,000198501167167.00204.0012,298.0070.9059.930.210.2700.81 1.29
t501_17 [log]1,000196501167167.00206.0012,169.0070.5359.880.190.2701.52 1.98
t501_18 [log]1,000193501167167.00202.0011,724.0070.9860.400.180.2703.25 3.70
t501_19 [log]1,000192501167167.00200.0011,761.0071.2259.440.180.2400.55 0.97
Arc-flow Vector Packing Solver
Copyright © Filipe Brandão