Implementation issues in optimization algorithms: do they matter?. Issue 4 (4th July 2019)

• Record Type: Journal Article
• Authors: Weise, Thomas; Wu, Yuezhong; Liu, Weichen; Chiong, Raymond
• Is Part Of: Journal of experimental & theoretical artificial intelligence. Volume 31:Issue 4(2019)
• Page Start: 533
• Page End: 554
• Publication Date: 2019-07-04
• Subjects: Optimization -- implementation issues -- traveling salesman problem -- Lin-Kernighan Heuristic -- Ejection Chain Method; Artificial intelligence -- Periodicals; 006.3
• DOI: 10.1080/0952813X.2019.1574908
• Languages: English
• ISSNs: 0952-813X

Abstract

ABSTRACT: Two factors that have a major impact on the performance of an optimization method are (1) formal algorithm specifications and (2) practical implementations. The impact of the latter is typically ignored, although it defines the results measured in experiments. We present an in-depth study of algorithm implementation issues and ask questions such as Does optimizing the implementation of an optimization algorithm pay off? Do bugs matter? and Is using more complicated but also more efficient data structures worth the effort? The intuitive answer to all of these questions is yes, but there is little published evidence. To bridge this gap, we use one of the most studied combinatorial optimization problems – the Traveling Salesman Problem – as a test bed and implement two state-of-the-art approaches for solving it – the Lin-Kernighan Heuristic and an Ejection Chain Method. We investigate implementation effort and performance gain, in order to provide further insights to the above questions.