qiskit.optimization.applications.ising.tsp

Convert symmetric TSP instances into Pauli list Deal with TSPLIB format. It supports only EUC_2D edge weight type. See https://wwwproxy.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ and http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html Design the tsp object w as a two-dimensional np.array e.g., w[i, j] = x means that the length of a edge between i and j is x Note that the weights are symmetric, i.e., w[j, i] = x always holds.

Functions

calc_distance(coord[, name])	calculate distance
get_operator(ins[, penalty])	Generate Hamiltonian for TSP of a graph.
get_tsp_solution(x)	Get graph solution from binary string.
parse_tsplib_format(filename)	Read graph in TSPLIB format from file.
random_tsp(n[, low, high, savefile, seed, name])	Generate a random instance for TSP.
tsp_feasible(x)	Check whether a solution is feasible or not.
tsp_value(z, w)	Compute the TSP value of a solution.

Classes

TspData(name, dim, coord, w)

Create new instance of TspData(name, dim, coord, w)

class TspData(name, dim, coord, w)

Create new instance of TspData(name, dim, coord, w)

property coord

Alias for field number 2

count(value, /)

Return number of occurrences of value.

property dim

Alias for field number 1

index(value, start=0, stop=9223372036854775807, /)

Return first index of value.

Raises ValueError if the value is not present.

property name

Alias for field number 0

property w

Alias for field number 3

calc_distance(coord, name='tmp')

calculate distance

get_operator(ins, penalty=100000.0)

Generate Hamiltonian for TSP of a graph.

Parameter

• ins (TspData) – TSP data including coordinates and distances.

• penalty (float) – Penalty coefficient for the constraints

Rückgabe

operator for the Hamiltonian and a constant shift for the obj function.

Rückgabetyp

tuple(WeightedPauliOperator, float)

get_tsp_solution(x)

Get graph solution from binary string.

Parameter

x (numpy.ndarray) – binary string as numpy array.

Rückgabe

sequence of cities to traverse.

The i-th item in the list corresponds to the city which is visited in the i-th step. The list for an infeasible answer e.g. [[0,1],1,] can be interpreted as visiting [city0 and city1] as the first city, then visit city1 as the second city, then visit no where as the third city).

Rückgabetyp

list[int]

logger = <Logger qiskit.optimization.applications.ising.tsp (WARNING)>

Instance data of TSP

parse_tsplib_format(filename)

Read graph in TSPLIB format from file.

Parameter

filename (str) – name of the file.

Rückgabe

instance data.

Rückgabetyp

TspData

random_tsp(n, low=0, high=100, savefile=None, seed=None, name='tmp')

Generate a random instance for TSP.

Parameter

• n (int) – number of nodes.

• low (float) – lower bound of coordinate.

• high (float) – upper bound of coordinate.

• savefile (str or None) – name of file where to save graph.

• seed (int or None) – random seed - if None, will not initialize.

• name (str) – name of an instance

Rückgabe

instance data.

Rückgabetyp

TspData

tsp_feasible(x)

Check whether a solution is feasible or not.

Parameter

x (numpy.ndarray) – binary string as numpy array.

Rückgabe

feasible or not.

Rückgabetyp

bool

tsp_value(z, w)

Compute the TSP value of a solution.

Parameter

• z (list[int]) – list of cities.

• w (numpy.ndarray) – adjacency matrix.

Rückgabe

value of the cut.

Rückgabetyp

float