Source code for dwave_networkx.algorithms.tsp

# Copyright 2018 D-Wave Systems Inc.
#
#    Licensed under the Apache License, Version 2.0 (the "License");
#    you may not use this file except in compliance with the License.
#    You may obtain a copy of the License at
#
#        http://www.apache.org/licenses/LICENSE-2.0
#
#    Unless required by applicable law or agreed to in writing, software
#    distributed under the License is distributed on an "AS IS" BASIS,
#    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#    See the License for the specific language governing permissions and
#    limitations under the License.
#
# =============================================================================
from __future__ import division

import itertools

from collections import defaultdict

from dwave_networkx.utils import binary_quadratic_model_sampler

__all__ = ["traveling_salesperson",
           "traveling_salesperson_qubo",
           "traveling_salesman",
           "traveling_salesman_qubo",
           "is_hamiltonian_path",
           ]


[docs]@binary_quadratic_model_sampler(1) def traveling_salesperson(G, sampler=None, lagrange=None, weight='weight', start=None, **sampler_args): """Returns an approximate minimum traveling salesperson route. Defines a QUBO with ground states corresponding to the minimum routes and uses the sampler to sample from it. A route is a cycle in the graph that reaches each node exactly once. A minimum route is a route with the smallest total edge weight. Parameters ---------- G : NetworkX graph The graph on which to find a minimum traveling salesperson route. This should be a complete graph with non-zero weights on every edge. sampler : A binary quadratic model sampler. A sampler is a process that samples from low energy states in models defined by an Ising equation or a Quadratic Unconstrained Binary Optimization Problem (QUBO). A sampler is expected to have a 'sample_qubo' and 'sample_ising' method. A sampler is expected to return an iterable of samples, in order of increasing energy. If no sampler is provided, one must be provided using the `set_default_sampler` function. lagrange : number, optional (default None) Lagrange parameter to weight constraints (visit every city once) versus objective (shortest distance route). weight : optional (default 'weight') The name of the edge attribute containing the weight. start : node, optional If provided, the route will begin at `start`. sampler_args : Additional keyword parameters are passed to the sampler. Returns ------- route : list List of nodes in order to be visited on a route Examples -------- >>> import dimod ... >>> G = nx.Graph() >>> G.add_weighted_edges_from({(0, 1, .1), (0, 2, .5), (0, 3, .1), (1, 2, .1), ... (1, 3, .5), (2, 3, .1)}) >>> dnx.traveling_salesperson(G, dimod.ExactSolver(), start=0) # doctest: +SKIP [0, 1, 2, 3] Notes ----- Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample. """ # Get a QUBO representation of the problem Q = traveling_salesperson_qubo(G, lagrange, weight) # use the sampler to find low energy states response = sampler.sample_qubo(Q, **sampler_args) sample = response.first.sample route = [None]*len(G) for (city, time), val in sample.items(): if val: route[time] = city if start is not None and route[0] != start: # rotate to put the start in front idx = route.index(start) route = route[-idx:] + route[:-idx] return route
traveling_salesman = traveling_salesperson
[docs]def traveling_salesperson_qubo(G, lagrange=None, weight='weight'): """Return the QUBO with ground states corresponding to a minimum TSP route. If :math:`|G|` is the number of nodes in the graph, the resulting qubo will have: * :math:`|G|^2` variables/nodes * :math:`2 |G|^2 (|G| - 1)` interactions/edges Parameters ---------- G : NetworkX graph A complete graph in which each edge has a attribute giving its weight. lagrange : number, optional (default None) Lagrange parameter to weight constraints (no edges within set) versus objective (largest set possible). weight : optional (default 'weight') The name of the edge attribute containing the weight. Returns ------- QUBO : dict The QUBO with ground states corresponding to a minimum travelling salesperson route. The QUBO variables are labelled `(c, t)` where `c` is a node in `G` and `t` is the time index. For instance, if `('a', 0)` is 1 in the ground state, that means the node 'a' is visted first. """ N = G.number_of_nodes() if lagrange is None: # If no lagrange parameter provided, set to 'average' tour length. # Usually a good estimate for a lagrange parameter is between 75-150% # of the objective function value, so we come up with an estimate for # tour length and use that. if G.number_of_edges()>0: lagrange = G.size(weight=weight)*G.number_of_nodes()/G.number_of_edges() else: lagrange = 2 # some input checking if N in (1, 2) or len(G.edges) != N*(N-1)//2: msg = "graph must be a complete graph with at least 3 nodes or empty" raise ValueError(msg) # Creating the QUBO Q = defaultdict(float) # Constraint that each row has exactly one 1 for node in G: for pos_1 in range(N): Q[((node, pos_1), (node, pos_1))] -= lagrange for pos_2 in range(pos_1+1, N): Q[((node, pos_1), (node, pos_2))] += 2.0*lagrange # Constraint that each col has exactly one 1 for pos in range(N): for node_1 in G: Q[((node_1, pos), (node_1, pos))] -= lagrange for node_2 in set(G)-{node_1}: # QUBO coefficient is 2*lagrange, but we are placing this value # above *and* below the diagonal, so we put half in each position. Q[((node_1, pos), (node_2, pos))] += lagrange # Objective that minimizes distance for u, v in itertools.combinations(G.nodes, 2): for pos in range(N): nextpos = (pos + 1) % N # going from u -> v Q[((u, pos), (v, nextpos))] += G[u][v][weight] # going from v -> u Q[((v, pos), (u, nextpos))] += G[u][v][weight] return Q
traveling_salesman_qubo = traveling_salesperson_qubo def is_hamiltonian_path(G, route): """Determines whether the given list forms a valid TSP route. A travelling salesperson route must visit each city exactly once. Parameters ---------- G : NetworkX graph The graph on which to check the route. route : list List of nodes in the order that they are visited. Returns ------- is_valid : bool True if route forms a valid travelling salesperson route. """ return (set(route) == set(G))