Augmented neural networks and problem structure-based heuristics for the bin-packing problem

Abstract

In this article, we report on a research project where we applied augmented-neural-networks (AugNNs) approach for solving the classical bin-packing problem (BPP). AugNN is a metaheuristic that combines a priority rule heuristic with the iterative search approach of neural networks to generate good solutions fast. This is the first time this approach has been applied to the BPP. We also propose a decomposition approach for solving harder BPP, in which subproblems are solved using a combination of AugNN approach and heuristics that exploit the problem structure. We discuss the characteristics of problems on which such problem structure-based heuristics could be applied. We empirically show the effectiveness of the AugNN and the decomposition approach on many benchmark problems in the literature. For the 1210 benchmark problems tested, 917 problems were solved to optimality and the average gap between the obtained solution and the upper bound for all the problems was reduced to under 0.66% and computation time averaged below 33 s per problem. We also discuss the computational complexity of our approach.

Keywords:

• bin packing
• heuristics
• neural networks
• optimisation

Notes

1. http://www.wiwi.uni-jena.de/Entscheidung/binpp/index.htm, last accessed on 5 January 2011.

2. http://www.apdio.pt/sicup/Sicuphomepage/research.htm, last accessed on 1 May 2004.