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) |
TspData
class TspData(name, dim, coord, w)
Create new instance of TspData(name, dim, coord, w)
coord
Alias for field number 2
count
count(value, /)
Return number of occurrences of value.
dim
Alias for field number 1
index
index(value, start=0, stop=9223372036854775807, /)
Return first index of value.
Raises ValueError if the value is not present.
name
Alias for field number 0
w
Alias for field number 3
calc_distance
get_operator
get_operator(ins, penalty=100000.0)
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
get_tsp_solution(x)
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
Default value: <Logger qiskit.optimization.applications.ising.tsp (WARNING)>
Instance data of TSP
parse_tsplib_format
parse_tsplib_format(filename)
Read graph in TSPLIB format from file.
Parameters
filename (str) – name of the file.
Returns
instance data.
Return type
random_tsp
random_tsp(n, low=0, high=100, savefile=None, seed=None, name='tmp')
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
tsp_feasible
tsp_feasible(x)
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
tsp_value(z, w)
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