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.

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*. — Sebastian Schmidt, Oct 07 '20 at 06:14

score 5 · Answer 1 · answered Oct 07 '20 at 08:57

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).

score 4 · Accepted Answer · answered Oct 01 '20 at 14:00

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.

Solving the (Directed) Hamiltonian Cycle problem

2 Answers2