# Solving the (Directed) Hamiltonian Cycle problem

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.

• What arc costs are you using? Oct 2, 2020 at 13:04
• Hi, I am using 10 for arcs that are in the graph, and 12 for arcs that are not. Then the nice transformation you linked works. Also, for infinity I use something like 10*<amount of nodes>. Oct 7, 2020 at 6:14

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.