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 Type Description
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:

Name Type Description Default
ax Axes | None

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

 None

Returns:

Type Description
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:

Name Type Description Default
data TspData | None

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

 None
ax Axes | None

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

 None

Returns:

Type Description
Axes

The axes with the plot.

Raises:

Type Description
ValueError

If data is None.

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:

Type Description
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:

Name Type Description Default
max_runtime float

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

 3600
quiet bool

Suppress the SCIP solver output.

 True

Returns:

Type Description
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:

Type Description
ValueError

If max_runtime is not positive.