A new lower bound for the bin-packing problem and its integration into the Martello–Toth procedure

In this paper a new lower bound for the Bin-Packing Problem (BPP) is introduced. This bound has been derived from the (standard one-dimensional) cutting Stock Problem which can be looked upon as a high multiplicity version of the BPP. By means of extensive numerical experiments the superiority of this new bound over existing bounds is demonstrated. It is also shown how the bound can be integrated into MTP (Martello–Toth-Procedure) and what improvements can be achieved in terms of solution quality and computing times. Furthermore, this modification of MTP, called MTPCS here, is compared to BISON, a hybrid method proposed only recently for the BPP.