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

Nihat Kasap and Anurag Agarwal

International Journal of Systems Science, 2012, vol. 43, issue 8, 1412-1430

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.

Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207721.2010.549587 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tsysxx:v:43:y:2012:i:8:p:1412-1430

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TSYS20

DOI: 10.1080/00207721.2010.549587

Access Statistics for this article

International Journal of Systems Science is currently edited by Visakan Kadirkamanathan

More articles in International Journal of Systems Science from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().