Skip to content

Traveling Salesperson Problem (TSP) API Reference

Data

Data model for Tsp use case.

TspData

Bases: UcData

Data for the Traveling Salesperson Problem (TSP) use case.

This class encapsulates all necessary information to define and solve a TSP instance. The TSP is a classic optimization problem where the goal is to find the shortest route that visits all cities exactly once and returns to the starting city.

Attributes:

  • name (Literal['traveling_salesperson_problem']) –

    A constant identifier for this data type, always set to "traveling_salesperson_problem". Used for registration and type identification in the use case registry.

  • city_names (list[str | int]) –

    A list of city identifiers (strings or integers) representing all cities in the problem instance. The order in this list corresponds to rows/columns in the distance_matrix. Example: ["New York", "Los Angeles", "Chicago"] or [0, 1, 2]

  • distance_matrix (SymMatrix) –

    A 2D NumPy array containing distances between all pairs of cities. The element at [i, j] represents the distance from city i to city j. For undirected TSP, this matrix is typically symmetric (distance[i,j] == distance[j,i]). Shape must be (n_cities, n_cities) where n_cities = len(city_names). Example: 3x3 matrix for 3 cities with distance values.

  • start_city (str) –

    The identifier of the starting city (must be one of city_names). The TSP route begins and ends at this city, returning after visiting all others. Example: "New York" if using string identifiers.

  • city_position ((dict[str, tuple[float, float]] | None, optional)) –

    Optional dictionary mapping each city identifier to its (x, y) coordinates in 2D space. Useful for:

    • Visualizing the TSP instance and its solution
    • Computing Euclidean distances when needed
    • Geographic or spatial analysis of the route

    If None, distances are purely abstract/given by distance_matrix. Example: {"New York": (40.7128, -74.0060), "Los Angeles": (34.0522, -118.2437)}

Examples:

Create a simple 3-city TSP instance:

>>> tsp = TspData(
...     name="traveling_salesperson_problem",
...     city_names=["A", "B", "C"],
...     distance_matrix=np.array([[0, 10, 15], [10, 0, 20], [15, 20, 0]]),
...     start_city="A",
...     city_position={"A": (0.0, 0.0), "B": (10.0, 0.0), "C": (5.0, 8.66)},
... )

plot(*, ax: Axes | None = None) -> Axes

Plot the TSP city layout as a NetworkX graph.

Cities are drawn as nodes connected by edges weighted by their distance. When city_position is available the nodes are placed at their given coordinates; otherwise a spring layout is computed automatically. The start city is highlighted in a distinct colour.

Parameters:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the TSP data.

from_graph(graph: nx.Graph, start_city: str) -> TspData staticmethod

Create TspData from a NetworkX graph.

from_distance_matrix(distance_matrix: np.ndarray, city_names: Sequence[str | int], start_city: str, city_position: dict[str, tuple[float, float]] | None = None) -> TspData staticmethod

Create TspData from a distance matrix.

Formulation

Formulation for Tsp use case.

TspFormulation

Bases: UcFormulation[TspData, TspSolution]

Formulation for the Tsp use case.

to_string(data: TspData) -> str staticmethod

Return a string describing the formulation.

formulate(data: TspData) -> Model staticmethod

Formulate the use case as a quantum optimization model.

interpret(solution: Solution, data: TspData) -> TspSolution staticmethod

Interpret the quantum solution.

Solution

Solution model for Tsp use case.

TspSolution

Bases: UcSolution

Solution for the Tsp use case.

plot(data: TspData | None = None, *, ax: Axes | None = None) -> Axes

Plot the TSP solution tour as a NetworkX graph.

All city-pairs are drawn as background edges; the tour is overlaid as directed (arrowed) edges. When data carries city_position the nodes are placed at their given coordinates; otherwise a spring layout is computed automatically.

Parameters:

  • data (TspData | None, default: None ) –

    Problem data. Required so that city positions can be visualised alongside the tour.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

Raises:

to_string() -> str

Return a string describing the solution.

Instance

Instance model for Tsp use case.

TspInstance

Bases: UcInstance[TspData, TspFormulation, TspSolution]

Instance combining data and formulation for Tsp.

Collection

Collection of Tsp instances.

TspCircleCollection

Bases: UcInstanceCollection[TspInstance]

Collection of Tsp instances.

generate(min_num_cities: int | None = None, max_num_cities: int | None = None, radius: float = 100.0, center: tuple[float, float] = (0.0, 0.0), num_instances: int = 1, *, sizes: Sequence[int] | None = None) -> TspCircleCollection classmethod

Generate TSP instances by placing cities equally on a circle.

Args: min_num_cities: Minimum number of cities per instance max_num_cities: Maximum number of cities per instance radius: Radius of the circle (in km) center: Center coordinates (x, y) of the circle num_instances: Number of instances to generate for each city count sizes: Explicit city counts to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_num_cities/max_num_cities

Returns:

  • TSPCircleSet: Set containing generated circle-based TSP problems –

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

  • max_runtime (float, default: 3600 ) –

    SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • list[bool] –

    Feasibility mask over the instances as they were before filtering, in that order: True where the instance was kept, False where it was removed.

Raises: