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.
| Original language | English |
|---|---|
| Pages | 231-237 |
| Number of pages | 7 |
| DOIs | |
| Publication status | Published - 2020 |
Keywords
- Multi-objective optimization
- Discrete optimization problems
- Branching algorithm
- Hamiltonian cycle problem
Project and Funding Information
- Funding Info
- This project was funded by the ELKARTEK Research Programme of the Basque Government (project KK-2019/00068). This work has been possible thanks to the support of the computing infrastructure of the i2BASQUE academic network. The work of Roberto Santana was funded by the Basque Government (project IT-1244-19), and Spanish Ministry of Economy and Competitiveness MINECO (project TIN2016-78365-R).