Show simple item record

dc.contributor.authorMurua, M.
dc.contributor.authorGalar, D.
dc.contributor.authorSantana, R.
dc.date.accessioned2022-02-16T12:17:54Z
dc.date.available2022-02-16T12:17:54Z
dc.date.issued2022-04
dc.identifier.citationMurua, M., D. Galar, and R. Santana. “Solving the Multi-Objective Hamiltonian Cycle Problem Using a Branch-and-Fix Based Algorithm.” Journal of Computational Science 60 (April 2022): 101578. doi:10.1016/j.jocs.2022.101578.en
dc.identifier.issn1877-7503en
dc.identifier.urihttp://hdl.handle.net/11556/1271
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.sponsorshipThis 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 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).en
dc.language.isoengen
dc.publisherElsevieren
dc.titleSolving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithmen
dc.typearticleen
dc.identifier.doi10.1016/j.jocs.2022.101578en
dc.rights.accessRightsopenAccessen
dc.subject.keywordsGraph theoryen
dc.subject.keywordsMulti-objective optimizationen
dc.subject.keywordsDiscrete optimization problemsen
dc.subject.keywordsHamiltonian cycle problemen
dc.subject.keywordsBranching algorithmen
dc.journal.titleJournal of Computational Scienceen
dc.page.initial101578en
dc.volume.number60en


Files in this item

Thumbnail

    Show simple item record