I am looking to solve a variant of the traveling salesman problem with a certain set of constraints:
- the graph is not complete, i.e. some nodes are not connected to each other
- the weight of an edge between any pair of connected nodes is always 1
What is the best way to model and solve this problem?
AFAIK the Concorde TSP solver, for example, requires real numbers for edge weights. And it seems like because all the edges have the same weight, there could be more than one valid solution.