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')[source]¶: calculate distance

get_operator(ins, penalty=100000.0)[source]¶

Generate Hamiltonian for TSP of a graph.

Parameters

ins (TspData) – TSP data including coordinates and distances.
penalty (float) – Penalty coefficient for the constraints

Returns

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

Return type

tuple(WeightedPauliOperator, float)

get_tsp_solution(x)[source]¶

Get graph solution from binary string.

Parameters

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

Returns

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).

Return type

list[int]

logger = <Logger qiskit.optimization.applications.ising.tsp (WARNING)>¶: Instance data of TSP

parse_tsplib_format(filename)[source]¶

Read graph in TSPLIB format from file.

Parameters: filename (str) – name of the file.
Returns: instance data.
Return type: TspData

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

Generate a random instance for TSP.

Parameters

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

Returns

instance data.

Return type

TspData

tsp_feasible(x)[source]¶

Check whether a solution is feasible or not.

Parameters: x (numpy.ndarray) – binary string as numpy array.
Returns: feasible or not.
Return type: bool

tsp_value(z, w)[source]¶

Compute the TSP value of a solution.

Parameters

z (list[int]) – list of cities.
w (numpy.ndarray) – adjacency matrix.

Returns

value of the cut.

Return type

float