Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm

Simple item page
dc.contributor.authorMurua, M.
dc.contributor.authorGalar, D.
dc.contributor.authorSantana, R.
dc.contributor.institutionFACTORY
dc.contributor.institutionTecnalia Research & Innovation
dc.date.issued2022-04
dc.descriptionPublisher Copyright: © 2022 Elsevier B.V.
dc.description.abstractThe 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.en
dc.description.statusPeer reviewed
dc.format.extent1
dc.format.extent548242
dc.identifier.citationMurua , 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
dc.identifier.doi10.1016/j.jocs.2022.101578
dc.identifier.issn1877-7503
dc.identifier.otherresearchoutputwizard: 11556/1271
dc.identifier.urlhttp://www.scopus.com/inward/record.url?scp=85124240005&partnerID=8YFLogxK
dc.language.isoeng
dc.relation.ispartofJournal of Computational Science
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subject.keywordsGraph theory
dc.subject.keywordsMulti-objective optimization
dc.subject.keywordsDiscrete optimization problems
dc.subject.keywordsHamiltonian cycle problem
dc.subject.keywordsBranching algorithm
dc.subject.keywordsGraph theory
dc.subject.keywordsMulti-objective optimization
dc.subject.keywordsDiscrete optimization problems
dc.subject.keywordsHamiltonian cycle problem
dc.subject.keywordsBranching algorithm
dc.subject.keywordsTheoretical Computer Science
dc.subject.keywordsGeneral Computer Science
dc.subject.keywordsModeling and Simulation
dc.subject.keywordsFunding Info
dc.subject.keywordsThis 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).
dc.subject.keywordsThis 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).
dc.titleSolving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithmen
dc.typejournal article
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Accepted_Manuscript.pdf
Size:
535.39 KB
Format:
Adobe Portable Document Format
Description:
Download