Browsing by Keyword "Branching algorithm"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Adaptation of a Branching Algorithm to Solve the Multi-Objective Hamiltonian Cycle Problem(Springer, Cham, 2020) Murua, Maialen; Galar, Diego; Santana, RobertoThe 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.Item Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm(2022-04) Murua, M.; Galar, D.; Santana, R.; FACTORY; Tecnalia Research & InnovationThe 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.