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

Kasap, Nihat and Agarwal, Anurag (2012) Augmented neural networks and problem-structure based heuristics for the bin-packing problem. International Journal of Systems Science, 43 (8). pp. 1412-1430. ISSN 0020-7721 (print) ; 1464-5319 (online)

This is the latest version of this item.

[thumbnail of Kasap_2012_IJSS.pdf] PDF
Restricted to Registered users only

Download (389kB) | Request a copy


In this paper, we apply the Augmented-neural-networks (AugNN) 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 sub problems 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 seconds per problem. We also discuss the computational complexity of our approach.
Item Type: Article
Uncontrolled Keywords: bin packing; heuristics; neural networks; optimisation
Divisions: Sabancı Business School
Sabancı Business School > Operations Management and Information Systems
Depositing User: Nihat Kasap
Date Deposited: 16 Oct 2012 12:08
Last Modified: 26 Apr 2022 08:57

Available Versions of this Item

Actions (login required)

View Item
View Item