qiskit-optimization icon indicating copy to clipboard operation
qiskit-optimization copied to clipboard

Updating TSP formulation to use less binary variables by fixing start city

Open abhamra opened this issue 5 months ago • 0 comments

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.

abhamra avatar Jun 24 '25 14:06 abhamra