TSP_inst

Generates TSP instances by sampling nodes from TSPLIB files.

USAGE:: python -m TSP_inst ./instances

Generates a set of TSP instances, saving original instance data in ./instances (or another specified directory): orig subdirectory for original instances and QUBO, respectively, for QUBOs.

Instance parameters are specified in main(), which in turn calls the core generation function, generate_TSP_instances(). This module also contains a few cross-checks (e.g., alternative MIP models), auxiliary and visualization code.

Functions

`assert_TSP_MIP`(instance_file, qubo_model, qubo_x)	Asserts if the solutions to QUBO and 'natural' MIP coincide.
`calc_distances`(problem)	Returns the distance matrix for `problem` (from `tsp.load`).
`create_MTZ_TSP_model`(D[, quiet])	Creates an MTZ model from distance matrix `D`.
`create_simple_TSP_model`(D[, quiet])	Creates a MIP model (QAP form) from distance matrix D for cross-check.
`draw_IDs_grid`(sel_IDs[, directory, Ncols, ...])	Draws a grid of instances by (the number part of) IDs.
`draw_inst_grid`(selected_files[, Ncols, ...])	Draws a grid of instances from `selected_files`.
`draw_instance`(G[, ax, node_color, ...])	Draws a single TSP instance (weighted graph `G`).
`encode_constraints`(Q, P, A, b, M)	Utility to create a QUBO: incorporates constraints in the form "Ax=b".
`generate_TSP_instances`([downloads, instdir, ...])	The core function that generates TSP instances.
`get_QF_coeffs`(D)	Builds TSP quadratic cost function coefficients from a graph.
`get_constraints`(D)	Returns the constraints for TSP in the matrix form.
`get_correct_dist`(NC, i, j)	Calculates the distance between i and j from node_coords `NC`.
`is_feasible`(tour, D)	Checks if `tour` is feasible (given the distance matrix `D`).
`k`(i, t, N)	Helper: returns the (linear) vector-index (k) given the matrix-indices (i,t).
`load_instance_by_ID`(ID[, directory])	Loads an instance by ID and returns matrix D.
`main`()	The main function specifying instance generation parameters (see the source code).
`obj_val`(D, tour)	Calculates the objective given the costs matrix and a tour.
`pt_to_ddeg`(val)	Converts single lat/lon value (`val`): Deg.Min to decimal degrees.
`sample_nodes`(Dfull[, Ns, K])	Creates distance matrices for sub-graphs of given size.
`save_orig_instance`(D, inst_id, problem[, ...])	Saves a TSP instance encoded by a distance matrix to a JSON (with metadata).
`show_feasible`(tour, D)	Wraps `is_feasible()` into a string, for readability.
`solve_TSP_MIP`(instance_file[, quiet, timeout])	Creates and solves a QAP MIP model for TSP.
`solve_TSP_MTZ`(instance_file[, quiet, timeout])	Creates and solves a MTZ MIP model for TSP.
`unpack_tour_QUBO_bitstring`(bs, N)	Unpacks the tour given the bitstring (assuming QUBO).
`unpack_tour_x`(x, N)	Returns the tour given gurobi vars (linear indexing) and the number of nodes.
`unpack_tour_y`(y, N)	Returns the tour given gurobi vars (matrix indexing) and the number of nodes.

TSP_inst.pt_to_ddeg(val)[source]: Converts single lat/lon value (val): Deg.Min to decimal degrees.

TSP_inst.get_correct_dist(NC, i, j)[source]: Calculates the distance between i and j from node_coords NC.

TSP_inst.calc_distances(problem)[source]: Returns the distance matrix for problem (from tsp.load).

TSP_inst.k(i, t, N)[source]

Helper: returns the (linear) vector-index (k) given the matrix-indices (i,t).

k: (i,t) -> N*t + i

Notes

Both i and t numbering is assumed zero-based. N is the total number of nodes addressed by i.

TSP_inst.get_QF_coeffs(D)[source]

Builds TSP quadratic cost function coefficients from a graph.

Parameters:

D – distance matrix, (N x N)

Returns:

Q – an (N-1)^2 x (N-1)^2 matrix of quadratic coefficients,
P – a vector of (N-1)^2 numbers containing linear coefficients.

Note

The resulting form is assumed to be (1/2) x’ Q x + P’ x.

TSP_inst.encode_constraints(Q, P, A, b, M)[source]

Utility to create a QUBO: incorporates constraints in the form “Ax=b”.

Parameters:

Q – quadratic coefficients matrix,
P – linear coefficients vector,
A – constraints matrix,
b – constraints RHS vector,
M – big M parameter (multiplicative const) for penalty terms.

Returns:

Q-prime, P-prime, and Const

Notes

We assume the input problem in the form:

min_x (1/2) x’ Q x + P’ x (1)

s.t. Ax = b

The function transforms it to:

min_x (1/2) x’ Qp x + Pp’ x + Const, (2)

where Qp and Pp incorporate penalties (with multiple M) into the objective, so that solutions to (1) and (2) would be the same.

TSP_inst.get_constraints(D)[source]

Returns the constraints for TSP in the matrix form.

Parameters:: D – the distance matrix,
Returns:: Matrix A and vector b, so that the constraints are Ax = b, assuming x-variables.

TSP_inst.save_orig_instance(D, inst_id, problem, comment='', directory='./instances/orig/')[source]

Saves a TSP instance encoded by a distance matrix to a JSON (with metadata).

Parameters:

D – distance matrix,
inst_id (string) – instance ID,
problem – original problem (as loaded by tsplib),
comment – optional comment for the JSON file,
directory – a dir to save files.

TSP_inst.load_instance_by_ID(ID, directory='./instances/orig/')[source]: Loads an instance by ID and returns matrix D.

TSP_inst.sample_nodes(Dfull, Ns=[5], K=5)[source]

Creates distance matrices for sub-graphs of given size.

Try to create K unique instances by generating N-node subgraphs from a weighted graph given by distance matrix Dfull.

Parameters:

Dfull (np.array) – full distance matrix,
N (list) – numbers of nodes to sample (default: one value, 5),
K (int) – number of samples to make per size (default: 5).

Example

>>> seed(2023)
>>> t = np.array([[1,2,3],[4,5,6],[7,8,9]])
>>> sample_nodes(t, Ns=2, K=3)
[array([[5, 6],
            [8, 9]]),
 array([[1, 3],
            [7, 9]]),
 array([[1, 2],
            [4, 5]])]

TSP_inst.generate_TSP_instances(downloads='./download/', instdir='./instances', Ns=[5, 7, 10], K=1, N_src_inst=15, Ninst_max=1000, N_total=100, seed=2023)[source]

The core function that generates TSP instances.

Creates at least K * len(Ns) and at most N_total instances by sampling from existing TSP instances (looked for in downloads directory) and saves them to directory instdir.

Parameters:

downloads (str) – a directory with original instances to sample from
instdir (str) – directory for the generated instances,
Ns (list[int]) – number of nodes to sample
K (int) – number of instances to create per size
N_src_inst (int) – max # of source TSP instances to process.
N_N (int) – max # of source TSP instances to process.
seed (int) – random seed, for reproducibility

TSP_inst.create_MTZ_TSP_model(D, quiet=False)[source]

Creates an MTZ model from distance matrix D.

Note

All numberings start from one.

Returns:: A model (gurobipy.Model), x, u (variables in the form of dict-s)

TSP_inst.create_simple_TSP_model(D, quiet=False)[source]

Creates a MIP model (QAP form) from distance matrix D for cross-check.

Parameters:: D – distance matrix,
Returns:: model (gurobipy.Model) and y (a dict of variables).

TSP_inst.unpack_tour_y(y, N)[source]

Returns the tour given gurobi vars (matrix indexing) and the number of nodes.

Parameters:

y – a dict of variables returned by Gurobi, keyed by (i, t),
N – number of nodes in the graph

TSP_inst.unpack_tour_QUBO_bitstring(bs, N)[source]: Unpacks the tour given the bitstring (assuming QUBO).

Note

Assumes direct order of bits in the bistring. E.g., [n0, n1, n2, ... ].

TSP_inst.unpack_tour_x(x, N)[source]

Returns the tour given gurobi vars (linear indexing) and the number of nodes.

Parameters:

x – a dict of variables returned by Gurobi, keyed by a single number k(i, t, N-1),
N – number of nodes in the graph

TSP_inst.is_feasible(tour, D)[source]

Checks if tour is feasible (given the distance matrix D).

Essentially, checks if the number of nodes is correct, all nodes are visited once, and the last point coincides with the first one.

TSP_inst.show_feasible(tour, D)[source]: Wraps is_feasible() into a string, for readability.

TSP_inst.obj_val(D, tour)[source]: Calculates the objective given the costs matrix and a tour.

TSP_inst.draw_instance(G, ax=<Axes: >, node_color='blue', node_size=200, with_labels=True)[source]: Draws a single TSP instance (weighted graph G).

TSP_inst.draw_inst_grid(selected_files, Ncols=3, directory='./instances-new/QUBO', cross_check=True)[source]

Draws a grid of instances from selected_files.

Parameters:

selected_files (list) – list of files (*.qubo.json)
Ncols (int) – number of columns in the grid.
directory (str) – directory with QUBO files (*.qubo.json)

TSP_inst.draw_IDs_grid(sel_IDs, directory='./instances-new/QUBO', Ncols=3, cross_check=True)[source]

Draws a grid of instances by (the number part of) IDs.

Parameters:

sel_IDs (list[int]) – list of instance IDs (numbers)
directory (str) – directory with QUBO files (*.qubo.json)
Ncols (int) – number of columns in the grid

Returns:

selected file names.

TSP_inst.solve_TSP_MIP(instance_file, quiet=True, timeout=None)[source]: Creates and solves a QAP MIP model for TSP.

TSP_inst.solve_TSP_MTZ(instance_file, quiet=True, timeout=None)[source]: Creates and solves a MTZ MIP model for TSP.

TSP_inst.assert_TSP_MIP(instance_file, qubo_model, qubo_x, quiet=True, tol=0.001, timeout=None) → None[source]: Asserts if the solutions to QUBO and ‘natural’ MIP coincide.

TSP_inst.main()[source]: The main function specifying instance generation parameters (see the source code).