A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs
- PDF / 656,557 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 18 Downloads / 212 Views
A multi-start local search algorithm for the Hamiltonian completion problem on undirected graphs Jorik Jooken1
· Pieter Leyman1
· Patrick De Causmaecker1
Received: 26 April 2019 / Revised: 17 February 2020 / Accepted: 21 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper proposes a local search algorithm for a specific combinatorial optimisation problem in graph theory: the Hamiltonian completion problem (HCP) on undirected graphs. In this problem, the objective is to add as few edges as possible to a given undirected graph in order to obtain a Hamiltonian graph. This problem has mainly been studied in the context of various specific kinds of undirected graphs (e.g. trees, unicyclic graphs and series-parallel graphs). The proposed algorithm, however, concentrates on solving HCP for general undirected graphs. It can be considered to belong to the category of matheuristics, because it integrates an exact linear time solution for trees into a local search algorithm for general graphs. This integration makes use of the close relation between HCP and the minimum path partition problem, which makes the algorithm equally useful for solving the latter problem. Furthermore, a benchmark set of problem instances is constructed for demonstrating the quality of the proposed algorithm. A comparison with state-of-the-art solvers indicates that the proposed algorithm is able to achieve high-quality results. Keywords Metaheuristics · Matheuristics · Combinatorial optimisation · Hamiltonian completion problem · Minimum path partition problem
We gratefully acknowledge the support provided by the ORDinL project (FWO-SBO S007318N, Data Driven Logistics, 1/1/2018–31/12/2021). Pieter Leyman is a Postdoctoral Fellow of the Research Foundation—Flanders (FWO) with contract number 12P9419N. The computational resources and services used in this work were provided by the VSC (Flemish Supercomputer Center), funded by the Research Foundation—Flanders (FWO) and the Flemish Government—Department EWI.
B
Jorik Jooken [email protected] Pieter Leyman [email protected] Patrick De Causmaecker [email protected]
1
Department of Computer Science, CODeS, KU Leuven Kulak, Etienne Sabbelaan 53, 8500 Kortrijk, Belgium
123
J. Jooken et al.
1 Introduction The problem of determining whether a given undirected graph contains a Hamiltonian cycle is one of Karp’s famous 21 NP-complete problems (Karp 1972). Being such a famous problem, it has been studied intensively for many years by the research community. This research has also led to many variations of this problem. One such variation is an interesting generalisation of the original problem in an optimisation context: the Hamiltonian completion problem (HCP), which is the main topic of this paper. In this paper, we develop a matheuristic (Boschetti et al. 2009) for HCP on undirected graphs. We will identify a restricted version of this problem that can be solved exactly in polynomial time. The solution of this restricted p
Data Loading...
