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

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

Name | Type | Description | #Solved | #Total |

Bin Packing | BPP | 1D Bin-Packing Problems from FALKENAUER (1996). | 160 | 160 |

Scholl | BPP | 1D Bin-Packing Problems from SCHOLL/KLEIN/JUERGENS (1997). | 1210 | 1210 |

Hard28 | BPP | The 28 VERY hard BPP instances of J. Schoenfield (with m from 140 to 200). | 28 | 28 |

SCH/WAE | BPP | 1D Bin-Packing Problems from SCHWERIN/WAESCHER (1998). | 200 | 200 |

WAE/GAU | BPP | 1D Bin-Packing Problems from WAESCHER/GAU (1996). | 17 | 17 |

Cutting Stock | CSP | 1D Bin-Packing Problems from FALKENAUER (1996) [demand x 10^6]. | 160 | 160 |

Cutgen | CSP | CUTGEN (Gau and Wascher, 1995). | 1800 | 1800 |

Fiber | CSP | Instances taken from a real application in a paper tube industry in Japan. | 39 | 39 |

Bin Packing Card | Card | Instances from FALKENAUER (1996) [with cardinality constraints]. | 720 | 720 |

Scholl Card | Card | 1D Bin-Packing Problems from SCHOLL/KLEIN/JUERGENS (1997) [with cardinality constraints]. | 3748 | 3748 |

Hard28 Card | Card | The 28 VERY hard BPP instances of J. Schoenfield (with m from 140 to 200) [with cardinality constraints]. | 56 | 56 |

SCH/WAE Card | Card | 1D Bin-Packing Problems from SCHWERIN/WAESCHER (1998) [with cardinality constraints]. | 1000 | 1000 |

WAE/GAU Card | Card | 1D Bin-Packing Problems from WAESCHER/GAU (1996) [with cardinality constraints]. | 131 | 131 |

Cutting Stock Card | Card | Instances from FALKENAUER (1996) [demand x 10^6; with cardinality constraints]. | 320 | 320 |

Cutgen Card | Card | CUTGEN (Gau and Wascher, 1995) [with cardinality constraints]. | 7299 | 7299 |

Fiber Card | Card | Instances taken from a real applications in a paper tube industry in Japan [with cardinality constraints]. | 279 | 279 |

Two-Constraint BPP | 2CBP | Two-Constraint Bin Packing instances of Spieksma/Caprara/Toth. | 320 | 400 |

Label | Description |

z | optimum objective value |

lb_lp | arc flow linear relaxation lower bound |

lb_sp | space lower bound |

lb_crd | cardinality lower bound |

lb_sp1 | space lower bound in the first dimension |

lb_sp2 | space lower bound in the second dimension |

lb_lp1 | arc flow linear relaxation lower bound in the first dimension |

lb_lp2 | arc flow linear relaxation lower bound in the second dimension |

W | bin capacity |

C | cardinality limit |

W1 | capacity of the first dimension |

W2 | capacity of the second dimension |

n | number of items |

m | number of different item sizes |

#vi | number of vertices in step i graph |

#ai | number of arcs in step i graph (including the final loss arcs) |

%v | ratio between the number of vertices after compression and the initial number of vertices |

%a | ratio between the number of arcs after compression and the initial number of arcs |

n_bb | number of nodes explored in the branch-and-bound procedure |

t_pp | time spent in pre/post-processing (seconds) |

t_lp | time spent in the linear relaxation of the root node (seconds) |

t_ip | time spent in the branch and bound procedure (seconds) |

tt | total run time (seconds) |

op | number of open instances solved |

ffd | first fit decreasing solution |

bfd | best fit decreasing solution |

a_* | absolute gap |h-z| |

r_* | relative gap (h-z)/z |

2ffd | 2D first fit decreasing solution |

2bfd | 2D 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)] |