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

Kasap, Nihat and Agarwal, Anurag (2010) Augmented neural networks and problem-structure based heuristics for the bin-packing problem. (Accepted/In Press)

Warning
There is a more recent version of this item available.
[thumbnail of Kasap_Agarwal_AugNNforBPP_Oct2010.pdf] PDF
Kasap_Agarwal_AugNNforBPP_Oct2010.pdf

Download (358kB)

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, Optimization
Divisions: Sabancı Business School
Sabancı Business School > Operations Management and Information Systems
Depositing User: Nihat Kasap
Date Deposited: 15 Dec 2010 11:18
Last Modified: 26 Apr 2022 08:44
URI: https://research.sabanciuniv.edu/id/eprint/16151

Available Versions of this Item

Actions (login required)

View Item
View Item