TY - Journal Article AU - Murua, Maialen AU - Galar, Diego AU - Santana, Roberto TI - Adaptation of a Branching Algorithm to Solve the Multi-Objective Hamiltonian Cycle Problem PY - 2020 PB - Springer, Cham AB - The Hamiltonian cycle problem (HCP) consists of finding a cycle of length N in an N-vertices graph. In this investigation, a graph G is considered with an associated set of matrices, in which each cell in the matrix corresponds to the weight of an arc. Thus, a multi-objective variant of the HCP is addressed and a Pareto set of solutions that minimizes the weights of the arcs for each objective is computed. To solve the HCP problem, the Branch-and-Fix algorithm is employed, a specific branching algorithm that uses the embedding of the problem in a particular stochastic process. To address the multi-objective HCP, the Branch-and-Fix algorithm is extended by computing different Hamiltonian cycles and fathoming the branches of the tree at earlier stages. The introduced anytime algorithm can produce a valid solution at any time of the execution, improving the quality of the Pareto Set as time increases. SN - 0721-5924 UR - http://hdl.handle.net/11556/995 DX - 10.1007/978-3-030-48439-2_28 ER -