Old Results  Filipe Brandão's Homepage

Arc-flow Formulation (w/ graph compression) Results: 20CBP

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

20CBP

chart
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CLASS.193.893.827.226.598,312.00162,083.505.896.720.0340.22 352.84
CLASS.293.893.890.590.507.50107.750.010.000.00.00 0.01
CLASS.393.893.890.590.507.75108.250.010.000.00.00 0.01
CLASS.425.025.04.03.1218,301.0083,729.006.2022.620.021.45 50.27
CLASS.525.025.02.01.5664,444.00223,730.0029.700.140.043.36 73.20
CLASS.693.893.848.247.96123.00842.250.040.010.00.02 0.07
CLASS.793.893.848.248.00124.75884.750.040.010.00.02 0.07
CLASS.893.893.856.256.2562.25356.500.030.000.00.01 0.04
CLASS.958.358.318.318.222,008.0016,242.000.660.660.03.09 4.41
CLASS.1093.893.836.836.291,702.0020,640.751.700.760.01.43 3.89
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_1_25 [log]252587.06194.001,065.000.040.0100.03 0.09
CL_1_50 [log]50501514.421,010.007,224.000.270.1300.41 0.81
CL_1_100 [log]1001002928.745,358.0064,416.002.292.29031.70 36.28
CL_1_200 [log]2002005756.1526,686.00575,629.0020.9724.4601,328.75 1,374.18
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_2_25 [log]25252323.006.0034.000.010.0000.00 0.01
CL_2_50 [log]50504848.006.0059.000.010.0000.00 0.01
CL_2_100 [log]1001009898.005.00107.000.010.0000.00 0.01
CL_2_200 [log]200200193193.0013.00231.000.010.0000.00 0.01
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_3_25 [log]25252323.006.0034.000.010.0000.00 0.01
CL_3_50 [log]50504848.006.0059.000.010.0000.00 0.01
CL_3_100 [log]1001009898.006.00109.000.010.0000.00 0.01
CL_3_200 [log]200200193193.0013.00231.000.010.0000.00 0.01
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_4_25 [log]252543.1218,301.0083,729.006.2022.62021.45 50.27
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_5_25 [log]252521.5664,444.00223,730.0029.700.14043.36 73.20
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_6_25 [log]25251312.3332.00131.000.010.0000.01 0.01
CL_6_50 [log]50502626.0060.00283.000.010.0000.01 0.02
CL_6_100 [log]1001005252.00122.00713.000.030.0100.01 0.05
CL_6_200 [log]200200102101.50278.002,242.000.110.0300.05 0.19
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_7_25 [log]25251312.5030.00128.000.010.0000.00 0.01
CL_7_50 [log]50502625.5064.00314.000.010.0000.01 0.03
CL_7_100 [log]1001005252.00129.00779.000.030.0100.01 0.06
CL_7_200 [log]200200102102.00276.002,318.000.120.0300.05 0.19
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_8_25 [log]25252121.007.0038.000.010.0000.00 0.01
CL_8_50 [log]50503737.0018.00102.000.010.0000.00 0.01
CL_8_100 [log]1001006363.0060.00322.000.020.0000.01 0.03
CL_8_200 [log]200200104104.00164.00964.000.080.0100.01 0.10
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_9_25 [log]252587.67151.00725.000.030.0100.02 0.05
CL_9_50 [log]50501616.00703.003,684.000.140.0700.16 0.37
CL_9_100 [log]1001003131.005,170.0044,317.001.811.9109.08 12.80
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
CL_10_24 [log]24241010.0039.00269.000.010.0000.01 0.02
CL_10_51 [log]51512120.50106.001,239.000.050.0200.03 0.11
CL_10_99 [log]99993938.22534.006,627.000.500.1100.30 0.91
CL_10_201 [log]2012017776.426,129.0074,428.006.252.9005.36 14.52
Arc-flow Vector Packing Solver
Copyright © Filipe Brandão