Adaptation of a Branching Algorithm to Solve the Multi-Objective Hamiltonian Cycle Problem

Maialen Murua, Diego Galar, Roberto SantanaOR 2019 · OpenReview

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...

Figure