4 votes

Simple example of finding Hamiltonian path using Google OR-Tools?

You can use OR-tools' routing library, and more specifically the TSP solver, with the Python API. Note that since you do not want the last arc in your example, you are solving an open TSP. You can ...
user avatar
  • 10.1k
2 votes
Accepted

Equivalence of Shortest Hamiltonian Paths with a Starting Node to Traveling Salesman Problem

The correspondence is almost the same as your other question. Here, the starting node is specified, so you don't need a dummy node or dummy arcs out of the starting node. To go from H-path (with ...
user avatar
  • 21.8k
2 votes
Accepted

Equivalence of Shortest Hamiltonian Paths to Traveling Salesman Problem

Q1. You need bidirectional arcs to and from the dummy node $n+1$ because you don't know ahead of time which directions are needed to complete the tour. Exactly one arc will enter the dummy, and ...
user avatar
  • 21.8k
1 vote
Accepted

Simple example of finding Hamiltonian path using Google OR-Tools?

After reading some examples, I thought that I could use the AddAllowedAssignments constraint. I found some examples, and came up with a solution to my question, so here it is (I just renamed the nodes ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible