Solving the (Directed) Hamiltonian Cycle problem

Question

I need to solve instances of the Directed Hamiltonian Cycle Problem (DHCP). I know that I can reduce the problem to TSP and then use a TSP solver like concorde.

I am unable to figure out though how to make concorde abort when a Hamiltonian cycle was found, i.e. when it found a solution with a given (by the reduction) upper bound.

Does anyone know of a solver for DHCP itself, or a TSP solver that features early abort when a specified upper bound was reached?

EDIT: I wrote to the maintainer of concorde, and apparently the -u flag allows to specify a numeric upper bound on which the solver terminates as soon as it is reached.

Answer 1

As far as I know, Concorde solves only symmetric TSPs, but you can do a transformation like this one.

If you are trying to find any Hamiltonian cycle, you can use any arc costs, but constant costs (say, $c_{i,j}=1$ for all arcs) should yield an optimal solution faster than random costs. With constant costs, the solver will automatically stop at the first feasible solution; with random costs, the solver will have to keep searching to prove optimality.

Answer 2

If you just want to find Hamiltonian cycles in a directed graph, maybe have a look at LKH-3 the TSP solver developed by Keld Helsgaun: http://webhotel4.ruc.dk/~keld/research/LKH-3/. The solver is based on high-performance local-search heuristics. It was used by the Concorde team to find feasible solutions (then proved to be optimal by branch-and-cut approaches) to "world-record" TSP instances (for example, see http://www.math.uwaterloo.ca/~bico/papers/proof.pdf).