title   
  

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.

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
380Kb

Official URL: http://dx.doi.org/10.1080/00207721.2010.549587

Abstract

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
Subjects:UNSPECIFIED
ID Code:19319
Deposited By:Nihat Kasap
Deposited On:16 Oct 2012 12:08
Last Modified:16 Oct 2012 12:08

Available Versions of this Item

Repository Staff Only: item control page