Skip to content
This repository was archived by the owner on Jul 12, 2026. It is now read-only.
This repository was archived by the owner on Jul 12, 2026. It is now read-only.

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

Description

@abhamra

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 function, but please let me know if this is incorrect.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions