Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

A Causal Approach for Explaining Why a Heuristic Algorithm Outperforms Another in Solving an Instance Set of the Bin Packing Problem

Joaquín PérezContact Information, Laura Cruz2, Rodolfo PazosContact Information, Vanesa Landero1, Gerardo ReyesContact Information, Crispín Zavala1, Héctor Fraire2 and Verónica Pérez2

(1)  Departamento de Ciencias Computacionales, Centro Nacional de Investigación y Desarrollo Tecnológico (CENIDET), AP 5-164, Cuernavaca, 62490, México
(2)  División de Estudios de Posgrado e Investigación, Instituto Tecnológico de Ciudad Madero (ITCM), Cd. Madero, México
Abstract
The problem of algorithm selection for solving NP problems arises with the appearance of a variety of heuristic algorithms. The first works claimed the supremacy of some algorithm for a given problem. Subsequent works revealed that the supremacy of algorithms only applied to a subset of instances. However, it was not explained why an algorithm solved better an instances subset. In this respect, this work approaches the problem of explaining through causal modeling the interrelations between instances characteristics and the inner workings of algorithms. For validating the results of the proposed approach, a set of experiments was carried out in a study case of the Tabu Search algorithm applied to the Bin Packing problem. Finally, the proposed approach can be useful for redesigning the logic of heuristic algorithms and for justifying the use of an algorithm to solve an instance subset. This information could contribute to algorithm selection for NP-hard problems.

Contact Information Joaquín Pérez
Email: jperez@cenidet.edu.mx

Contact Information Rodolfo Pazos
Email: pazos@cenidet.edu.mx

Contact Information Gerardo Reyes
Email: greyes@cenidet.edu.mx
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.112 • Server: mpweb15
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)