dimod.generators.traveling_salesperson#

traveling_salesperson(graph: nx.Graph, lagrange: float | None = None, weight: str = 'weight', missing_edge_weight: float | None = None) → BinaryQuadraticModel[source]#

Return a binary quadratic model (BQM) with ground states corresponding to a minimum TSP route.

If \(|graph|\) is the number of nodes in the graph, the resulting qubo will have:

  • \(|graph|^2\) variables/nodes

  • \(2 |graph|^2 (|graph| - 1)\) interactions/edges

Parameters:

  • graph – A complete graph in which each edge has an attribute giving its weight, given as a NetworkX graph.

  • lagrange – Lagrange parameter to weight constraints (no edges within set) versus objective (largest set possible).

  • weight – The name of the edge attribute containing the weight, defaults to “weight”.

  • missing_edge_weight – For bi-directional graphs, the weight given to missing edges. If None is given (the default), missing edges will be set to the sum of all weights.

Returns:

A binary quadratic model (BQM) with ground states corresponding to a minimum traveling salesperson route. The BQM variables are labelled (c, t) where c is a node in graph and t is the time index. For instance, if ('a', 0) is 1 in the ground state, that means the node ‘a’ is visited first.