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

Maialen Murua (), Diego Galar and Roberto Santana
Additional contact information
Maialen Murua: TECNALIA
Diego Galar: TECNALIA
Roberto Santana: University of the Basque Country (UPV/EHU)

A chapter in Operations Research Proceedings 2019, 2020, pp 231-237 from Springer

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

Keywords: Multi-objective optimization; Discrete optimization problems; Hamiltonian cycle problem; Branching algorithm (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-030-48439-2_28

Ordering information: This item can be ordered from
http://www.springer.com/9783030484392

DOI: 10.1007/978-3-030-48439-2_28

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().