Characterizing and Analyzing the Relation Between Bin-Packing Problem and Tabu Search Algorithm
- 1 October 2020
- book chapter
- Published by Springer Nature
- Vol. 12249, 149-164
Abstract
The relation between problem and solution algorithm presents a similar phenomenon in different research problems (optimization, decision, classification, ordering); the algorithm performance is very good in some cases of the problem, and very bad in other. Majority of related works have worked for predicting the most adequate algorithm to solve a new problem instance. However, the relation between problem and algorithm is not understood at all. In this paper a formal characterization of this relation is proposed to facilitate the analysis and understanding of the phenomenon. Case studies for Tabu Search algorithm and One Dimension Bin Packing problem were performed, considering three important sections of algorithm logical structure. Significant variables of problem structure and algorithm searching behavior from past experiments, metrics known by scientific community were considered (Autocorrelation Coefficient and Length) and significant variables of algorithm operative behavior were proposed. The models discovered in the case studies gave guidelines that permits to redesign algorithm logical structure, which outperforms to the original algorithm in an average of 69%. The proposed characterization for the relation problem-algorithm could be a formal procedure for obtaining guidelines that improves the algorithm performance.Keywords
This publication has 25 references indexed in Scilit:
- Algorithm runtime prediction: Methods & evaluationArtificial Intelligence, 2014
- Self-configuring data mining for ubiquitous computingInformation Sciences, 2013
- Development and analysis of constructive heuristic algorithms for flow shop scheduling problems with sequence-dependent setup timesThe International Journal of Advanced Manufacturing Technology, 2012
- Experimental evaluation of an automatic parameter setting systemExpert Systems with Applications, 2009
- Cross-disciplinary perspectives on meta-learning for algorithm selectionACM Computing Surveys, 2009
- Instance-Based Selection of Policies for SAT SolversLecture Notes in Computer Science, 2009
- New heuristics for one-dimensional bin-packingComputers & Operations Research, 2002
- Learning to Select Branching Rules in the DPLL Procedure for SatisfiabilityElectronic Notes in Discrete Mathematics, 2001
- No free lunch theorems for optimizationIEEE Transactions on Evolutionary Computation, 1997
- Evolutionary Heuristics for the Bin Packing Problem1995