Old Results  Filipe Brandão's Homepage

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

0-1 CSP FLK

chart
NAMEWMNZIPZLPVFAFTPRETLPNNTIPTTOT
binpack1150.063.2120,000,000.048,504,593.748,504,593.25487.352,491.650.100.070.60.26 0.43
binpack2150.077.2250,000,000.0101,094,408.9101,094,408.47752.753,706.750.240.160.00.57 0.97
binpack3150.080.8500,000,000.0200,637,011.7200,637,011.32832.354,060.650.280.190.00.68 1.15
binpack4150.081.01,000,000,000.0400,006,493.5400,006,493.15839.004,087.000.280.190.00.49 0.96
binpack51,000.050.060,000,000.020,000,562.620,000,562.5479.85708.250.030.010.00.04 0.09
binpack61,000.086.2120,000,000.040,000,000.040,000,000.00135.101,988.550.130.040.00.12 0.29
binpack71,000.0140.1249,000,000.083,000,000.083,000,000.00209.905,624.750.700.140.00.74 1.58
binpack81,000.0194.2501,000,000.0167,000,000.0167,000,000.00275.4511,836.601.920.340.02.28 4.54
NAMEWMNZIPZLPVFAFTPRETLPNNTIPTTOT
u120_00 [log]15058120,000,00047,269,50447,269,503.55428.002,168.000.080.0800.20 0.36
u120_01 [log]15059120,000,00048,064,51748,064,516.13453.002,305.000.090.0600.10 0.25
u120_02 [log]15061120,000,00045,293,33445,293,333.33608.002,809.000.130.1000.32 0.54
u120_03 [log]15068120,000,00048,625,95548,625,954.20594.002,916.000.140.0800.16 0.37
u120_04 [log]15062120,000,00049,101,35249,101,351.35443.002,306.000.110.0800.16 0.34
u120_05 [log]15061120,000,00047,489,79647,489,795.92477.002,374.000.090.0600.19 0.35
u120_06 [log]15065120,000,00047,580,00047,580,000.00588.002,837.000.140.1000.09 0.33
u120_07 [log]15064120,000,00048,659,86448,659,863.95406.002,266.000.090.0600.15 0.29
u120_08 [log]15067120,000,00049,918,36849,918,367.35584.002,909.000.130.0800.28 0.49
u120_09 [log]15064120,000,00045,802,72245,802,721.09599.002,877.000.120.0900.20 0.41
u120_10 [log]15064120,000,00051,292,68351,292,682.93452.002,385.000.100.0600.11 0.26
u120_11 [log]15060120,000,00048,411,11248,411,111.11376.002,018.000.070.0500.12 0.24
u120_12 [log]15063120,000,00047,866,66747,866,666.67562.002,801.000.110.08111.17 1.37
u120_13 [log]15062120,000,00048,013,33448,013,333.33489.002,456.000.100.0700.51 0.67
u120_14 [log]15061120,000,00049,172,41449,172,413.79389.002,136.000.080.0500.22 0.35
u120_15 [log]15063120,000,00047,384,05847,384,057.97503.002,513.000.100.0800.16 0.34
u120_16 [log]15064120,000,00051,391,30551,391,304.35379.002,158.000.080.0600.15 0.29
u120_17 [log]15064120,000,00051,500,00051,500,000.00327.002,020.000.070.0400.05 0.16
u120_18 [log]15066120,000,00048,387,75648,387,755.10488.002,608.000.100.0800.22 0.40
u120_19 [log]15068120,000,00048,867,13348,867,132.87602.002,971.000.130.1000.57 0.80
NAMEWMNZIPZLPVFAFTPRETLPNNTIPTTOT
u250_00 [log]15071250,000,00098,553,33498,553,333.33568.002,912.000.130.1000.42 0.65
u250_01 [log]15078250,000,00099,026,66799,026,666.67812.003,909.000.270.1800.73 1.19
u250_02 [log]15076250,000,000101,435,375101,435,374.10719.003,608.000.230.1600.36 0.75
u250_03 [log]15079250,000,00099,426,66799,426,666.67794.003,870.000.270.1900.68 1.14
u250_04 [log]15076250,000,000100,613,334100,613,333.30749.003,633.000.230.1500.70 1.08
u250_05 [log]15078250,000,000100,829,932100,829,932.00780.003,801.000.260.1600.75 1.16
u250_06 [log]15078250,000,000101,026,667101,026,666.70827.003,962.000.280.1800.43 0.89
u250_07 [log]15077250,000,000102,903,704102,903,703.70732.003,645.000.220.1701.49 1.88
u250_08 [log]15078250,000,000104,931,973104,931,972.80715.003,655.000.230.1400.71 1.09
u250_09 [log]15080250,000,000100,205,480100,205,479.50743.003,771.000.260.1600.31 0.74
u250_10 [log]15077250,000,000104,394,558104,394,557.80722.003,619.000.230.1600.44 0.84
u250_11 [log]15080250,000,000100,714,286100,714,285.70790.003,913.000.280.1901.18 1.66
u250_12 [log]15076250,000,000104,991,042104,991,041.40658.003,392.000.200.1400.20 0.54
u250_13 [log]15075250,000,000102,044,445102,044,444.40735.003,571.000.200.1500.35 0.70
u250_14 [log]15079250,000,00099,183,67499,183,673.47809.003,909.000.270.1600.78 1.22
u250_15 [log]15078250,000,000104,863,637104,863,636.40732.003,663.000.240.1700.47 0.88
u250_16 [log]15076250,000,00096,513,33496,513,333.33799.003,809.000.250.1600.53 0.95
u250_17 [log]15076250,000,00099,170,06999,170,068.03763.003,715.000.240.1400.30 0.68
u250_18 [log]15076250,000,00099,700,00099,700,000.00769.003,691.000.250.1700.24 0.65
u250_19 [log]15081250,000,000101,360,000101,360,000.00839.004,087.000.230.1700.29 0.69
NAMEWMNZIPZLPVFAFTPRETLPNNTIPTTOT
u500_00 [log]15081500,000,000197,580,000197,580,000.00839.004,087.000.300.1900.11 0.60
u500_01 [log]15081500,000,000200,846,667200,846,666.70839.004,087.000.270.1801.37 1.82
u500_02 [log]15080500,000,000201,440,000201,440,000.00815.003,967.000.300.1700.35 0.83
u500_03 [log]15081500,000,000203,813,334203,813,333.30839.004,087.000.310.2100.83 1.35
u500_04 [log]15080500,000,000205,113,334205,113,333.30743.003,771.000.210.1400.73 1.08
u500_05 [log]15081500,000,000205,086,667205,086,666.70839.004,087.000.280.2201.21 1.72
u500_06 [log]15081500,000,000206,905,798206,905,797.10839.004,087.000.280.2001.10 1.59
u500_07 [log]15080500,000,000203,980,000203,980,000.00827.004,010.000.290.2000.22 0.71
u500_08 [log]15081500,000,000195,680,000195,680,000.00839.004,087.000.260.1500.08 0.49
u500_09 [log]15081500,000,000201,060,000201,060,000.00839.004,087.000.290.1700.85 1.31
u500_10 [log]15081500,000,000199,066,667199,066,666.70839.004,087.000.240.1700.47 0.87
u500_11 [log]15081500,000,000199,426,667199,426,666.70839.004,087.000.290.1900.73 1.21
u500_12 [log]15081500,000,000198,620,000198,620,000.00839.004,087.000.300.2100.11 0.62
u500_13 [log]15081500,000,000195,586,667195,586,666.70839.004,087.000.300.1800.72 1.21
u500_14 [log]15081500,000,000203,041,096203,041,095.90839.004,087.000.300.2100.74 1.25
u500_15 [log]15080500,000,000200,133,334200,133,333.30838.004,073.000.280.1900.54 1.01
u500_16 [log]15081500,000,000201,006,667201,006,666.70839.004,087.000.320.2100.47 1.00
u500_17 [log]15081500,000,000197,426,667197,426,666.70839.004,087.000.290.2101.14 1.64
u500_18 [log]15081500,000,000201,293,334201,293,333.30839.004,087.000.230.1500.60 0.98
u500_19 [log]15081500,000,000195,633,334195,633,333.30839.004,087.000.310.2101.14 1.66
NAMEWMNZIPZLPVFAFTPRETLPNNTIPTTOT
u1000_00 [log]150811,000,000,000398,426,667398,426,666.70839.004,087.000.310.1900.77 1.27
u1000_01 [log]150811,000,000,000405,253,334405,253,333.30839.004,087.000.260.1800.69 1.13
u1000_02 [log]150811,000,000,000410,200,000410,200,000.00839.004,087.000.290.2100.36 0.87
u1000_03 [log]150811,000,000,000410,869,864410,869,863.00839.004,087.000.280.2000.33 0.81
u1000_04 [log]150811,000,000,000396,740,000396,740,000.00839.004,087.000.300.1800.14 0.62
u1000_05 [log]150811,000,000,000398,493,334398,493,333.30839.004,087.000.240.1900.98 1.41
u1000_06 [log]150811,000,000,000394,206,667394,206,666.70839.004,087.000.320.1800.52 1.01
u1000_07 [log]150811,000,000,000403,160,000403,160,000.00839.004,087.000.290.2000.16 0.64
u1000_08 [log]150811,000,000,000398,433,334398,433,333.30839.004,087.000.240.1400.72 1.10
u1000_09 [log]150811,000,000,000396,926,667396,926,666.70839.004,087.000.310.1600.54 1.02
u1000_10 [log]150811,000,000,000399,340,000399,340,000.00839.004,087.000.240.1900.10 0.52
u1000_11 [log]150811,000,000,000400,520,000400,520,000.00839.004,087.000.280.2000.10 0.58
u1000_12 [log]150811,000,000,000392,240,000392,240,000.00839.004,087.000.310.1800.23 0.72
u1000_13 [log]150811,000,000,000395,273,334395,273,333.30839.004,087.000.310.2000.51 1.03
u1000_14 [log]150811,000,000,000393,886,667393,886,666.70839.004,087.000.280.2101.26 1.76
u1000_15 [log]150811,000,000,000401,806,667401,806,666.70839.004,087.000.250.1700.47 0.89
u1000_16 [log]150811,000,000,000403,026,667403,026,666.70839.004,087.000.320.2000.77 1.28
u1000_17 [log]150811,000,000,000403,800,000403,800,000.00839.004,087.000.290.1900.22 0.70
u1000_18 [log]150811,000,000,000398,193,334398,193,333.30839.004,087.000.310.2000.43 0.94
u1000_19 [log]150811,000,000,000399,333,334399,333,333.30839.004,087.000.240.1900.45 0.88
NAMEWMNZIPZLPVFAFTPRETLPNNTIPTTOT
t60_00 [log]1,0005060,000,00020,001,30620,001,305.4879.00684.000.030.0100.23 0.27
t60_01 [log]1,0005660,000,00020,000,00020,000,000.0089.00796.000.050.0200.03 0.10
t60_02 [log]1,0004860,000,00020,000,00020,000,000.0079.00646.000.040.0100.02 0.07
t60_03 [log]1,0004960,000,00020,000,00020,000,000.0076.00707.000.030.0100.02 0.07
t60_04 [log]1,0004860,000,00020,000,00020,000,000.0077.00709.000.040.0200.01 0.07
t60_05 [log]1,0005060,000,00020,000,00020,000,000.0079.00711.000.030.0100.02 0.06
t60_06 [log]1,0005160,000,00020,000,00020,000,000.0081.00745.000.040.0200.02 0.09
t60_07 [log]1,0005060,000,00020,000,88220,000,881.0681.00711.000.030.0100.05 0.09
t60_08 [log]1,0004960,000,00020,000,00020,000,000.0078.00682.000.030.0200.02 0.08
t60_09 [log]1,0004960,000,00020,006,49420,006,493.5177.00683.000.030.0100.11 0.15
t60_10 [log]1,0005360,000,00020,000,00020,000,000.0084.00793.000.040.0200.05 0.11
t60_11 [log]1,0004660,000,00020,000,00020,000,000.0075.00644.000.030.0200.01 0.06
t60_12 [log]1,0005360,000,00020,000,00020,000,000.0084.00767.000.040.0100.02 0.08
t60_13 [log]1,0005160,000,00020,000,00020,000,000.0082.00753.000.030.0100.05 0.09
t60_14 [log]1,0005060,000,00020,002,57120,002,570.6982.00688.000.030.0100.02 0.06
t60_15 [log]1,0005160,000,00020,000,00020,000,000.0081.00703.000.030.0100.02 0.06
t60_16 [log]1,0004660,000,00020,000,00020,000,000.0074.00642.000.030.0100.02 0.05
t60_17 [log]1,0004860,000,00020,000,00020,000,000.0075.00673.000.030.0100.02 0.06
t60_18 [log]1,0005060,000,00020,000,00020,000,000.0080.00742.000.040.0100.02 0.07
t60_19 [log]1,0005160,000,00020,000,00020,000,000.0084.00686.000.030.0100.02 0.06
NAMEWMNZIPZLPVFAFTPRETLPNNTIPTTOT
t120_00 [log]1,00086120,000,00040,000,00040,000,000.00135.001,936.000.130.0300.06 0.22
t120_01 [log]1,00085120,000,00040,000,00040,000,000.00131.001,995.000.120.0400.08 0.25
t120_02 [log]1,00091120,000,00040,000,00040,000,000.00148.002,148.000.150.0400.10 0.29
t120_03 [log]1,00086120,000,00040,000,00040,000,000.00136.001,914.000.130.0400.08 0.25
t120_04 [log]1,00092120,000,00040,000,00040,000,000.00143.002,241.000.160.0400.12 0.32
t120_05 [log]1,00088120,000,00040,000,00040,000,000.00138.002,026.000.140.0400.10 0.27
t120_06 [log]1,00086120,000,00040,000,00040,000,000.00136.001,974.000.130.0300.10 0.26
t120_07 [log]1,00087120,000,00040,000,00040,000,000.00134.002,074.000.130.0400.50 0.67
t120_08 [log]1,00086120,000,00040,000,00040,000,000.00134.002,019.000.130.0300.04 0.20
t120_09 [log]1,00085120,000,00040,000,00040,000,000.00135.001,919.000.120.0400.07 0.23
t120_10 [log]1,00083120,000,00040,000,00040,000,000.00133.001,832.000.120.0300.06 0.21
t120_11 [log]1,00086120,000,00040,000,00040,000,000.00135.001,908.000.130.0300.20 0.36
t120_12 [log]1,00082120,000,00040,000,00040,000,000.00126.001,902.000.110.0300.04 0.18
t120_13 [log]1,00087120,000,00040,000,00040,000,000.00134.002,005.000.130.0400.09 0.26
t120_14 [log]1,00083120,000,00040,000,00040,000,000.00128.001,760.000.110.0300.07 0.22
t120_15 [log]1,00081120,000,00040,000,00040,000,000.00130.001,704.000.110.0300.04 0.18
t120_16 [log]1,00087120,000,00040,000,00040,000,000.00135.002,053.000.130.0400.46 0.63
t120_17 [log]1,00090120,000,00040,000,00040,000,000.00143.002,209.000.150.0300.05 0.23
t120_18 [log]1,00085120,000,00040,000,00040,000,000.00134.002,012.000.120.0400.04 0.21
t120_19 [log]1,00087120,000,00040,000,00040,000,000.00134.002,140.000.140.0500.09 0.28
NAMEWMNZIPZLPVFAFTPRETLPNNTIPTTOT
t249_00 [log]1,000134249,000,00083,000,00083,000,000.00201.005,169.000.500.1000.89 1.50
t249_01 [log]1,000140249,000,00083,000,00083,000,000.00208.005,622.000.580.1100.28 0.97
t249_02 [log]1,000139249,000,00083,000,00083,000,000.00208.005,389.000.740.1700.26 1.17
t249_03 [log]1,000142249,000,00083,000,00083,000,000.00212.005,975.000.640.1302.01 2.78
t249_04 [log]1,000134249,000,00083,000,00083,000,000.00201.005,163.000.610.1200.96 1.69
t249_05 [log]1,000145249,000,00083,000,00083,000,000.00216.005,950.000.810.1500.43 1.39
t249_06 [log]1,000138249,000,00083,000,00083,000,000.00203.005,692.000.690.1400.27 1.10
t249_07 [log]1,000137249,000,00083,000,00083,000,000.00207.005,497.000.650.1300.37 1.16
t249_08 [log]1,000139249,000,00083,000,00083,000,000.00211.005,494.000.730.1400.42 1.29
t249_09 [log]1,000141249,000,00083,000,00083,000,000.00210.005,681.000.620.1300.15 0.90
t249_10 [log]1,000140249,000,00083,000,00083,000,000.00208.005,670.000.700.1200.78 1.60
t249_11 [log]1,000141249,000,00083,000,00083,000,000.00213.005,740.000.730.1500.25 1.12
t249_12 [log]1,000141249,000,00083,000,00083,000,000.00212.005,600.000.740.1500.22 1.11
t249_13 [log]1,000141249,000,00083,000,00083,000,000.00210.005,813.000.780.1701.50 2.45
t249_14 [log]1,000145249,000,00083,000,00083,000,000.00220.005,727.000.820.1701.46 2.45
t249_15 [log]1,000142249,000,00083,000,00083,000,000.00214.005,601.000.770.1400.44 1.35
t249_16 [log]1,000144249,000,00083,000,00083,000,000.00212.005,939.000.770.1800.30 1.25
t249_17 [log]1,000145249,000,00083,000,00083,000,000.00219.005,884.000.690.1502.49 3.33
t249_18 [log]1,000138249,000,00083,000,00083,000,000.00209.005,372.000.700.1501.05 1.90
t249_19 [log]1,000136249,000,00083,000,00083,000,000.00204.005,517.000.650.1700.27 1.10
NAMEWMNZIPZLPVFAFTPRETLPNNTIPTTOT
t501_00 [log]1,000190501,000,000167,000,000167,000,000.00269.0011,542.002.010.3403.97 6.32
t501_01 [log]1,000192501,000,000167,000,000167,000,000.00272.0011,493.002.090.3302.31 4.73
t501_02 [log]1,000190501,000,000167,000,000167,000,000.00272.0010,901.002.130.3301.99 4.45
t501_03 [log]1,000199501,000,000167,000,000167,000,000.00283.0012,165.002.300.3801.11 3.80
t501_04 [log]1,000195501,000,000167,000,000167,000,000.00275.0011,854.002.220.4503.29 5.96
t501_05 [log]1,000195501,000,000167,000,000167,000,000.00273.0011,925.002.260.3400.60 3.20
t501_06 [log]1,000196501,000,000167,000,000167,000,000.00276.0012,061.002.320.4103.85 6.58
t501_07 [log]1,000192501,000,000167,000,000167,000,000.00274.0011,533.001.950.3402.71 5.00
t501_08 [log]1,000196501,000,000167,000,000167,000,000.00278.0012,174.001.770.2704.11 6.15
t501_09 [log]1,000189501,000,000167,000,000167,000,000.00271.0011,066.001.600.3303.18 5.10
t501_10 [log]1,000190501,000,000167,000,000167,000,000.00274.0011,309.001.610.3103.10 5.02
t501_11 [log]1,000195501,000,000167,000,000167,000,000.00276.0012,023.001.760.3003.09 5.15
t501_12 [log]1,000189501,000,000167,000,000167,000,000.00269.0011,246.001.580.2602.76 4.60
t501_13 [log]1,000198501,000,000167,000,000167,000,000.00279.0012,399.001.850.3802.75 4.98
t501_14 [log]1,000203501,000,000167,000,000167,000,000.00285.0012,902.002.040.3700.61 3.02
t501_15 [log]1,000197501,000,000167,000,000167,000,000.00278.0012,042.001.830.3200.95 3.10
t501_16 [log]1,000198501,000,000167,000,000167,000,000.00280.0012,342.001.880.3600.41 2.65
t501_17 [log]1,000196501,000,000167,000,000167,000,000.00279.0012,205.001.820.3103.69 5.81
t501_18 [log]1,000193501,000,000167,000,000167,000,000.00274.0011,763.001.690.3400.59 2.62
t501_19 [log]1,000192501,000,000167,000,000167,000,000.00272.0011,787.001.650.3000.53 2.48
Arc-flow Vector Packing Solver
Copyright © Filipe Brandão