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.

  • $\begingroup$ What arc costs are you using? $\endgroup$
    – RobPratt
    Oct 2 '20 at 13:04
  • $\begingroup$ 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>. $\endgroup$ Oct 7 '20 at 6:14

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.