Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm
Loading...
Identifiers
Publication date
2022-04
Authors
Advisors
Journal Title
Journal ISSN
Volume Title
Publisher
Citations
Export
Abstract
The Hamiltonian cycle problem consists of finding a cycle in a given graph that passes through every single vertex exactly once, or determining that this cannot be achieved. In this investigation, a graph is considered with an associated set of matrices. The entries of each of the matrix correspond to a different weight of an arc. A multi-objective Hamiltonian cycle problem is addressed here by computing a Pareto set of solutions that minimize the sum of the weights of the arcs for each objective. Our heuristic approach extends the Branch-and-Fix algorithm, an exact method that embeds the problem in a stochastic process. To measure the efficiency of the proposed algorithm, we compare it with a multi-objective genetic algorithm in graphs of a different number of vertices and density. The results show that the density of the graphs is critical when solving the problem. The multi-objective genetic algorithm performs better (quality of the Pareto sets) than the proposed approach in random graphs with high density; however, in these graphs it is easier to find Hamiltonian cycles, and they are closer to the multi-objective traveling salesman problem. The results reveal that, in a challenging benchmark of Hamiltonian graphs with low density, the proposed approach significantly outperforms the multi-objective genetic algorithm.
Description
Publisher Copyright: © 2022 Elsevier B.V.
Keywords
Graph theory , Multi-objective optimization , Discrete optimization problems , Hamiltonian cycle problem , Branching algorithm , Graph theory , Multi-objective optimization , Discrete optimization problems , Hamiltonian cycle problem , Branching algorithm , Theoretical Computer Science , General Computer Science , Modeling and Simulation , Funding Info , This work has been possible thanks to the support of the computing infrastructure of the i2BASQUE academic network. We would like to thank Dr. Haythorpe for providing the Matlab code of the original BF algorithm and addressing some of our questions on the algorithm_x000D_ and the implementation. Roberto Santana acknowledges support by the Spanish Ministry of Science and Innovation (projects TIN2016-78365-R and PID2019-104966GB-I00), and the Basque Government (projects KK-2020/00049 and IT1244-19, and ELKARTEK program). , This work has been possible thanks to the support of the computing infrastructure of the i2BASQUE academic network. We would like to thank Dr. Haythorpe for providing the Matlab code of the original BF algorithm and addressing some of our questions on the algorithm_x000D_ and the implementation. Roberto Santana acknowledges support by the Spanish Ministry of Science and Innovation (projects TIN2016-78365-R and PID2019-104966GB-I00), and the Basque Government (projects KK-2020/00049 and IT1244-19, and ELKARTEK program).
Type
Citation
Murua , M , Galar , D & Santana , R 2022 , ' Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm ' , Journal of Computational Science , vol. 60 , 101578 , pp. 101578 . https://doi.org/10.1016/j.jocs.2022.101578