Evolving test instances of the Hamiltonian completion problem. (January 2023)

• Record Type: Journal Article
• Authors: Lechien, Thibault; Jooken, Jorik; De Causmaecker, Patrick
• Is Part Of: Computers & operations research. Volume 149(2023)
• Publication Date: 2023-01
• Subjects: Evolving instances -- Instance space -- Hamiltonian completion problem; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106019
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Predicting and comparing algorithm performance on graph instances is challenging for multiple reasons. First, there is not always a standard set of instances to benchmark performance. Second, using existing graph generators results in a restricted spectrum of difficulty and the resulting graphs are not always diverse enough to draw sound conclusions. That is why recent work proposes a new methodology to generate a diverse set of instances by using evolutionary algorithms. We can then analyze the resulting graphs and get key insights into which attributes are most related to algorithm performance. We can also fill observed gaps in the instance space in order to generate graphs with previously unseen combinations of features. We apply this methodology to the instance space of the Hamiltonian completion problem using two different solvers, namely the Concorde TSP Solver and a multi-start local search algorithm. Highlights: Applied a novel methodology to generate very diverse and challenging test instances. Visualized the instance space, providing insights into each algorithm's performance. Showed that reducing dimensions retains key characteristics.