The logical structure of approximation algorithms has been identified by the scientific community in four principal parts: tuning parameters, generating initial solutions, generating neighbor solutions, and stopping algorithm execution. A review of the literature specifically for the algorithms Threshold Accepting (TA) and Tabu Search (TS) indicates that, in most cases, choices are performed on one or several of these logical parts, often implicitly guided by expert knowledge for improving algorithm performance. However, these design choices, particularly in the selection of initialization and neighborhood strategies, are rarely analyzed in a systematic and reproducible manner. A formal experimental framework is presented to systematically analyze logical structure design choices, which are typically based on empirical expertise, by isolating and evaluating the combined effects of methodologies in the logical parts of initialization and neighborhood under controlled conditions of TA and TS algorithms in solving the one-dimensional Bin Packing Problem (BPP). A total of 324 benchmark instances were used to assess multiple algorithmic variants. Performance was evaluated in terms of solution quality and computational effort, supported by graphical analysis and statistical methods, including Wilcoxon signed-rank tests, effect size measures, bootstrap-based confidence intervals, and linear regression. The experimental results consistently show that the simpler internal logical structure of TA and TS algorithms, specifically with a probability-guided initialization combined with a single neighborhood operator, can achieve a better balance between solution quality and computational effort compared to more complex alternatives in general instances of BPP.
Landero-Nájera et al. (Fri,) studied this question.