Old Results  Filipe Brandão's Homepage

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

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

Timetabling

chart
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
hdtt124.6180.030.030.0011,609.6095,098.007.83476.056.211,138.66 11,622.55
NAMEMNZIPZLPVFAFTPRETLPNNTIPTTOT
hdtt4 [log]591203030.00148.00906.000.030.0200.03 0.07
hdtt5 [log]881503030.00644.004,221.000.140.1500.29 0.58
hdtt6 [log]1251803030.002,719.0019,566.000.952.62012.51 16.08
hdtt7 [log]1542103030.0011,140.0082,725.005.5947.62161,697.31 1,750.52
hdtt8 [log]1972403030.0043,397.00368,072.0032.462,329.861553,983.17 56,345.49
Arc-flow Vector Packing Solver
Copyright © Filipe Brandão