Adaptation of a Branching Algorithm to Solve the Multi-Objective Hamiltonian Cycle Problem
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{murua2019adaptation,
author = {Maialen Murua and Diego Galar and Roberto Santana},
title = {{Adaptation of a Branching Algorithm to Solve the Multi-Objective Hamiltonian Cycle Problem}},
booktitle = {OR},
year = {2019},
url = {https://openreview.net/forum?id=9JLeSMDUOz},
}Loading related content...