Hacia la Caracterización de Instancias Difíciles del Problema de Bin Packing (Towards a Characterization of Difficult Instances of the Bin Packing Problem)

Adriana Mexicano Santoyo (mexicanoa@gmail.com)1, Joaquín Pérez Ortega (jpo_cenidet@yahoo.com.mx)2, David Romero (davidr@matcuer.unam.mx)3, Laura Cruz Reyes (lcruzr@prodigy.net.mx)4

1Instituto Tecnológico de Cd. Victoria

This paper appears in: Revista IEEE América Latina

Publication Date: July 2015
Volume: 13,   Issue: 7 
ISSN: 1548-0992

We address the multidimensional characterization of difficult instances of the Bin Packing Problem, well known in the combinatorial optimization realm. In search for efficient procedures to solve hard combinatorial optimization problems previous investigations have attempted to identify the instances' characteristics with the greatest impact in their difficulty. In the same vein and focusing on the Bin Packing Problem, we used clustering techniques to determine not only one but a set of characteristics that altogether could be considered as the main source of the instances difficulty. To this aim we selected 1,615 available instances of the Bin Packing Problem, and then we solved each instance with six well-known heuristic algorithms. From our experiment we identified relevant characteristics that correspond to 22 instances whose optimal solution was not obtained by any of the six heuristics. Finally, to validate our findings an adhoc heuristic based on these characteristics was developed. Our heuristic found two optimal solutions not previously reported, showing thus that this characterization can help to find improved solution algorithms.

Index Terms:
bin packing, combinatorial optimization, heuristics, NP-hard, clustering   

Documents that cite this document
This function is not implemented yet.

[PDF Full-Text (434)]