Characterization of Difficult Bin Packing Problem Instances oriented to Improve Metaheuristic Algorithms

Abstract

This work presents a methodology for characterizing difficult instances of the Bin Packing problem using Data Mining. The objective is that the instance’s characteristics help to provide some ideas for developing new strategies to find optimal solutions by improving the current solution algorithms or develop new ones. According to related work, in general, the instance characterization has been used to make a prediction of the algorithm that best solves an instance, or to improve one by associating the instance characteristics and performance of the algorithm that solves it. However, this work proposes the development of efficient solution algorithms guided by a previous identification of the characteristics that represent a greater impact on the difficulty of the instances. To validate our approach we used a set of 1,615 instances, 6 well-known algorithms of the Bin Packing Problem, and 27 initial metrics. After applying our approach, 5 metrics were found as relevant, this metrics helped to characterize 4 groups containing the instances that could not be solved by any of the algorithms used in this work. Based on the gained knowledge from the instance's characterization, a new reduction method that helps to reduce de search space of a metaheuristic algorithm was proposed. Experimental results show that applying the reduction method is able to find more optimal solutions than those reported in the specialized literature by the best metaheuristics.