modules.applications.optimization.tsp.tsp.TSP

class TSP

Bases: Optimization

"The famous travelling salesman problem (also called the travelling salesperson problem or in short TSP) is a well-known NP-hard problem in combinatorial optimization, asking for the shortest possible route that visits each node exactly once, given a list of nodes and the distances between each pair of nodes. Applications of the TSP can be found in planning, logistics, and the manufacture of microchips. In these applications, the general concept of a node represents, for example, customers, or points on a chip.

TSP as graph problem: The solution to the TSP can be viewed as a specific ordering of the vertices in a weighted graph. Taking an undirected weighted graph, nodes correspond to the graph's nodes, with paths corresponding to the graph's edges, and a path's distance is the edge's weight." (source: https://github.com/aws/amazon-braket-examples/tree/main/examples)

__init__()

Constructor method.

Methods

__init__()	Constructor method.
evaluate(solution)	Find distance for given route and original data.
generate_problem(config)	Uses the reference graph to generate a problem for a given config.
get_application()	Gets the application.
get_available_submodule_options()	Gets the list of available options.
get_available_submodules(option)	If the module has submodules depending on certain options, this method should adjust the submodule_options accordingly.
get_default_submodule(option)	Returns the default submodule based on the given option.
get_depending_parameters(option, config)	If the module has parameters depending on certain options, this method should return the parameters for the given option.
get_parameter_options()	Returns the configurable settings for this application
get_requirements()	Return requirements of this module.
get_solution_quality_unit()	Returns the unit of measurement for the solution quality.
get_submodule(option)	Submodule is instantiated according to the information given in self.sub_options.
postprocess(input_data, config, **kwargs)	For optimization problems, we process the solution here, then validate and evaluate it.
preprocess(input_data, config, **kwargs)	For optimization problems, we generate the actual problem instance in the preprocess function.
process_solution(solution)	Convert dict to list of visited nodes.
save(path, iter_count)	Save the current application state to a file.
validate(solution)	Checks if it is a valid TSP tour.
visualize_solution(processed_solution, path)	Plot a graph representing the problem network with the solution path highlighted

class Config

Bases: TypedDict

Attributes of a valid config.

nodes: int

clear() → None.  Remove all items from D.

copy() → a shallow copy of D

fromkeys(value=None, /)

Create a new dictionary with keys from iterable and values set to value.

get(key, default=None, /)

Return the value for key if key is in the dictionary, else default.

items() → a set-like object providing a view on D's items

keys() → a set-like object providing a view on D's keys

pop(k[, d]) → v, remove specified key and return the corresponding value.

If the key is not found, return the default if given; otherwise, raise a KeyError.

popitem()

Remove and return a (key, value) pair as a 2-tuple.

Pairs are returned in LIFO (last-in, first-out) order. Raises KeyError if the dict is empty.

setdefault(key, default=None, /)

Insert key with a value of default if key is not in the dictionary.

Return the value for key if key is in the dictionary, else default.

update([E, ]**F) → None.  Update D from mapping/iterable E and F.

If E is present and has a .keys() method, then does: for k in E.keys(): D[k] = E[k] If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v In either case, this is followed by: for k in F: D[k] = F[k]

values() → an object providing a view on D's values

evaluate(solution: list) → tuple[float, float]

Find distance for given route and original data.

Parameters:

solution -- List containing the nodes of the solution

Returns:

Tour cost and the time it took to calculate it

generate_problem(config: Config) → Graph

Uses the reference graph to generate a problem for a given config.

Parameters:

config -- Configuration dictionary

Returns:

Graph with the problem

get_application() → any

Gets the application.

Returns:

self.application

get_available_submodule_options() → list

Gets the list of available options.

Returns:

List of module options

get_available_submodules(option: list) → list

If the module has submodules depending on certain options, this method should adjust the submodule_options accordingly.

Parameters:

option -- List of chosen options

Returns:

List of available submodules

get_default_submodule(option: str) → Core

Returns the default submodule based on the given option.

Parameters:

option -- The chosen submodule option

Returns:

The corresponding submodule instance

Raises:

NotImplemented -- If the provided option is not implemented

get_depending_parameters(option: str, config: dict) → dict

If the module has parameters depending on certain options, this method should return the parameters for the given option.

Parameters:

• option -- The chosen option

• config -- Current config dictionary

Returns:

The parameters for the given option

get_parameter_options() → dict

Returns the configurable settings for this application

Returns:

Dictionary with configurable settings.

return {
        "nodes": {
            "values": list([3, 4, 6, 8, 10, 14, 16]),
            "allow_ranges": True,
            "description": "How many nodes does your graph need?",
            "postproc": int
        }
    }

static get_requirements() → list

Return requirements of this module.

Returns:

List of dict with requirements of this module

get_solution_quality_unit() → str

Returns the unit of measurement for the solution quality.

Returns:

Unit of measurement for the solution quality

get_submodule(option: str) → Core

Submodule is instantiated according to the information given in self.sub_options. If self.sub_options is None, get_default_submodule is called as a fallback.

Parameters:

option -- String with the options

Returns:

Instance of a module

postprocess(input_data: any, config: dict, **kwargs) → tuple[any, float]

For optimization problems, we process the solution here, then validate and evaluate it.

Parameters:

• input_data -- Data which should be evaluated for this optimization problem

• config -- Config for the problem creation

• kwargs -- Optional additional arguments

Returns:

Tuple with results and the postprocessing time

preprocess(input_data: any, config: dict, **kwargs) → tuple[any, float]

For optimization problems, we generate the actual problem instance in the preprocess function.

Parameters:

• input_data -- Input data (usually not used in this method)

• config -- Config for the problem creation

• kwargs -- Optional additional arguments

Returns:

Tuple with output and the preprocessing time

process_solution(solution: dict) → tuple[list, float]

Convert dict to list of visited nodes.

Parameters:

solution -- Dictionary with solution

Returns:

Processed solution and the time it took to process it

save(path: str, iter_count: int) → None

Save the current application state to a file.

Parameters:

• path -- The directory path where the file will be saved

• iter_count -- The iteration count to include in the filename

validate(solution: list) → tuple[bool, float]

Checks if it is a valid TSP tour.

Parameters:

solution -- List containing the nodes of the solution

Returns:

Boolean whether the solution is valid, time it took to validate

visualize_solution(processed_solution: list[int], path: str)

Plot a graph representing the problem network with the solution path highlighted

Parameters:

• processed_solution -- The solution already processed by process_solution(), a list of visited node IDs in order of being visited.

• path -- File path for the plot

Returns:

None