qiskit-optimization
qiskit-optimization copied to clipboard
Updating TSP formulation to use less binary variables by fixing start city
The canonical TSP conversion to QUBO for some $n$ cities results in $n^2$ binary variables, however we can reduce this to $(n-1)^2$ by fixing some starting city vacuously and figuring out the optimal tour ordering for every other node. Since the Tsp class itself only accepts complete graphs, this modification seems to be logically fine and would reduce the overall computational cost of Tsp overall.
My assumption is that we only have to modify the to_quadratic_program and interpret functions, but please let me know if this is incorrect.