Solving Multi-Objective Hamiltonian Cycle Problem Using a Branching Algorithm

The Hamiltonian cycle problem (HCP) finds a cycle of length N in an N-vertices graph. We consider a graph G with an associated set of matrices. The weight of each arc corresponds to a cell in the matrices. We consider a multi-objective variant of the HCP and compute a Pareto set of solutions that minimize the weights of arcs for each objective. The HCP problem can be solved using an embedded stochastic process using the Branch-and-Fix algorithm. We extend the Branch-and-Fix algorithm to address multi-objective HCPs by computing different Hamiltonian cycles and fathoming the tree branches at earlier stages. With the algorithm, a valid solution can be produced during the execution, which improves the quality of the Pareto Set over time.