New Results  Filipe Brandão's Homepage

Arc Flow Formulation (w/ graph compression) Results

Results for Brandão, F. (2012). Bin Packing and Related Problems: Pattern-Based Approaches. Master’s thesis
17,487 benchmark instances solved in 5 days (less than 25 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, Download Logs

total run time
graph reduction (vertices)graph reduction (arcs)
Bin PackingBPP1D Bin-Packing Problems from FALKENAUER (1996).160 160
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
Cutting StockCSP1D Bin-Packing Problems from FALKENAUER (1996) [demand x 10^6].160 160
CutgenCSPCUTGEN (Gau and Wascher, 1995).1800 1800
FiberCSPInstances taken from a real application in a paper tube industry in Japan.39 39
Bin Packing CardCardInstances from FALKENAUER (1996) [with cardinality constraints].720 720
Scholl CardCard1D Bin-Packing Problems from SCHOLL/KLEIN/JUERGENS (1997) [with cardinality constraints].3748 3748
Hard28 CardCardThe 28 VERY hard BPP instances of J. Schoenfield (with m from 140 to 200) [with cardinality constraints].56 56
SCH/WAE CardCard1D Bin-Packing Problems from SCHWERIN/WAESCHER (1998) [with cardinality constraints].1000 1000
WAE/GAU CardCard1D Bin-Packing Problems from WAESCHER/GAU (1996) [with cardinality constraints].131 131
Cutting Stock CardCardInstances from FALKENAUER (1996) [demand x 10^6; with cardinality constraints].320 320
Cutgen CardCardCUTGEN (Gau and Wascher, 1995) [with cardinality constraints].7299 7299
Fiber CardCardInstances taken from a real applications in a paper tube industry in Japan [with cardinality constraints].279 279
Two-Constraint BPP2CBPTwo-Constraint Bin Packing instances of Spieksma/Caprara/Toth.320 400
zoptimum objective value
lb_lparc flow linear relaxation lower bound
lb_spspace lower bound
lb_crdcardinality lower bound
lb_sp1space lower bound in the first dimension
lb_sp2space lower bound in the second dimension
lb_lp1arc flow linear relaxation lower bound in the first dimension
lb_lp2arc flow linear relaxation lower bound in the second dimension
Wbin capacity
Ccardinality limit
W1capacity of the first dimension
W2capacity of the second dimension
nnumber of items
mnumber of different item sizes
#vinumber of vertices in step i graph
#ainumber of arcs in step i graph (including the final loss arcs)
%vratio between the number of vertices after compression and the initial number of vertices
%aratio between the number of arcs after compression and the initial number of arcs
n_bbnumber of nodes explored in the branch-and-bound procedure
t_pptime spent in pre/post-processing (seconds)
t_lptime spent in the linear relaxation of the root node (seconds)
t_iptime spent in the branch and bound procedure (seconds)
tttotal run time (seconds)
opnumber of open instances solved
ffdfirst fit decreasing solution
bfdbest fit decreasing solution
a_*absolute gap |h-z|
r_*relative gap (h-z)/z
2ffd2D first fit decreasing solution
2bfd2D best fit decreasing solution [selecting the bin that minimizes s1/W1+s2/W2 where (s1,s2) is the currently available space (using decreasing lexicographic order in case of a tie)]
Copyright © Filipe Brandão