Premium
The Bin‐Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP
Author(s) -
Schwerin P.,
Wäscher G.
Publication year - 1997
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1997.tb00093.x
Subject(s) - bin packing problem , generator (circuit theory) , heuristic , packing problems , computer science , mathematical optimization , bin , algorithm , power (physics) , mathematics , physics , quantum mechanics
In this paper a problem generator for the Bin‐Packing Problem (BPP) is presented which is suggested to be used in future for the empirical evaluation of exact and heuristic solution methods. Also some numerical experiments are performed with FFD Packing in order to identify hard problem classes of the BPP. From the results it becomes evident that the design of a previous test by Martello and Toth, in which the authors tried to verify the solution power of their method, MTP, has been biased. Thus, new experiments with MTP have been performed on instances from more challenging problem classes. Our results confirm the general opinion that MTP represents the state‐or‐the‐art for exact solution methods for the BPP, even though the size of the problems, which can be solved to a proven optimum in reasonable computing time, still appears to be unsatisfactory.