discrete_optimization.tsp package

Subpackages

Submodules

discrete_optimization.tsp.mutation module

class discrete_optimization.tsp.mutation.Mutation2Opt(tsp_model: Point2DTspProblem, test_all: bool = False, nb_test: int | None = None, return_only_improvement: bool = False, **kwargs: Any)[source]

Bases: Mutation

static build(problem: Point2DTspProblem, solution: TspSolution, **kwargs) → Mutation2Opt[source]
get_points(it: int, jt: int, variable: TspSolution) → tuple[Point2D, Point2D, Point2D, Point2D][source]
get_points_index(it: int, jt: int, variable: TspSolution) → tuple[int, int, int, int][source]
mutate(variable: TspSolution) → tuple[TspSolution, LocalMove][source]
mutate_and_compute_obj(variable: TspSolution) → tuple[TspSolution, LocalMove, dict[str, float]][source]
node_count: int
points: Sequence[Point2D]
class discrete_optimization.tsp.mutation.Mutation2OptIntersection(tsp_model: Point2DTspProblem, test_all: bool = True, nb_test: int | None = None, return_only_improvement: bool = False, i_j_pairs: list[tuple[int, int]] | None = None, **kwargs: Any)[source]

Bases: Mutation2Opt

static build(problem: Point2DTspProblem, solution: TspSolution, **kwargs) → Mutation2OptIntersection[source]
mutate_and_compute_obj(variable: TspSolution) → tuple[TspSolution, LocalMove, dict[str, float]][source]
nodeCount: int
points: Sequence[Point2D]
class discrete_optimization.tsp.mutation.MutationSwapTsp(tsp_model: TspProblem)[source]

Bases: Mutation

static build(problem: TspProblem, solution: TspSolution, **kwargs) → MutationSwapTsp[source]
mutate(solution: TspSolution) → tuple[TspSolution, LocalMove][source]
mutate_and_compute_obj(solution: TspSolution) → tuple[TspSolution, LocalMove, dict[str, float]][source]
class discrete_optimization.tsp.mutation.SwapTspMove(attribute: str, tsp_model: TspProblem, swap: tuple[int, int])[source]

Bases: LocalMove

apply_local_move(solution: TspSolution) → TspSolution[source]
backtrack_local_move(solution: TspSolution) → TspSolution[source]
discrete_optimization.tsp.mutation.ccw(A: Point2D, B: Point2D, C: Point2D) → bool[source]
discrete_optimization.tsp.mutation.find_intersection(variable: TspSolution, points: Sequence[Point2D], test_all: bool = False, nb_tests: int = 10) → list[tuple[int, int]][source]
discrete_optimization.tsp.mutation.get_points_index(it: int, jt: int, variable: TspSolution, length_permutation: int) → tuple[int, int, int, int][source]
discrete_optimization.tsp.mutation.intersect(A: Point2D, B: Point2D, C: Point2D, D: Point2D) → bool[source]

discrete_optimization.tsp.parser module

discrete_optimization.tsp.parser.get_data_available(data_folder: str | None = None, data_home: str | None = None) → list[str][source]

Get datasets available for tsp.

Params:
data_folder: folder where datasets for tsp whould be find.

If None, we look in “tsp” subdirectory of data_home.

data_home: root directory for all datasets. Is None, set by

default to “~/discrete_optimization_data “

discrete_optimization.tsp.parser.parse_file(file_path: str, start_index: int = 0, end_index: int = 0) → Point2DTspProblem[source]
discrete_optimization.tsp.parser.parse_input_data(input_data: str, start_index: int = 0, end_index: int = 0) → Point2DTspProblem[source]

discrete_optimization.tsp.plot module

discrete_optimization.tsp.plot.plot_tsp_solution(tsp_model: Point2DTspProblem, solution: TspSolution, ax: Any | None = None) → None[source]

discrete_optimization.tsp.problem module

class discrete_optimization.tsp.problem.DistanceMatrixTspProblem(list_points: Sequence[Point], distance_matrix: ndarray, node_count: int, start_index: int = 0, end_index: int = 0, use_numba: bool = True)[source]

Bases: TspProblem

evaluate_function(var_tsp: TspSolution) → tuple[list[int], int][source]
evaluate_function_indexes(index_1: int, index_2: int) → float[source]
class discrete_optimization.tsp.problem.Point[source]

Bases: object

class discrete_optimization.tsp.problem.Point2D(x: float, y: float)[source]

Bases: Point

x: float
y: float
class discrete_optimization.tsp.problem.Point2DTspProblem(list_points: Sequence[Point2D], node_count: int, start_index: int = 0, end_index: int = 0, use_numba: bool = True)[source]

Bases: TspProblem

evaluate_function(var_tsp: TspSolution) → tuple[Iterable[float], float][source]
evaluate_function_indexes(index_1: int, index_2: int) → float[source]
list_points: Sequence[Point2D]
class discrete_optimization.tsp.problem.TspProblem(list_points: Sequence[Point], node_count: int, start_index: int = 0, end_index: int = 0)[source]

Bases: Problem

convert_original_perm_to_perm_from0(perm: Iterable[int]) → list[int][source]
convert_perm_from0_to_original_perm(perm_from0: Iterable[int]) → list[int][source]
evaluate(var_tsp: TspSolution) → dict[str, float][source]

Evaluate a given solution object for the given problem.

This method should return a dictionnary of KPI, that can be then used for mono or multiobjective optimization.

Parameters:

variable (Solution) – the Solution object to evaluate.

Returns: dictionnary of float kpi for the solution.

evaluate_from_encoding(int_vector: Iterable[int], encoding_name: str) → dict[str, float][source]
abstract evaluate_function(var_tsp: TspSolution) → tuple[Iterable[float], float][source]
abstract evaluate_function_indexes(index_1: int, index_2: int) → float[source]
get_attribute_register() → EncodingRegister[source]

Returns how the Solution should be encoded.

Returns (EncodingRegister): content of the encoding of the solution

get_dummy_solution() → TspSolution[source]
get_objective_register() → ObjectiveRegister[source]

Returns the objective definition.

Returns (ObjectiveRegister): object defining the objective criteria.

get_random_dummy_solution() → TspSolution[source]
get_solution_type() → type[Solution][source]

Returns the class implementation of a Solution.

Returns (class): class object of the given Problem.

list_points: Sequence[Point]
node_count: int
np_points: ndarray
satisfy(var_tsp: TspSolution) → bool[source]

Computes if a solution satisfies or not the constraints of the problem.

Parameters:

variable – the Solution object to check satisfability

Returns (bool): boolean true if the constraints are fulfilled, false elsewhere.

class discrete_optimization.tsp.problem.TspSolution(problem: TspProblem, start_index: int | None = None, end_index: int | None = None, permutation: list[int] | None = None, lengths: list[float] | None = None, length: float | None = None, permutation_from0: list[int] | None = None)[source]

Bases: Solution

change_problem(new_problem: Problem) → None[source]

If relevant to the optimisation problem, change the underlying problem instance for the solution.

This method can be used to evaluate a solution for different instance of problems.

Parameters:

new_problem (Problem) – another problem instance from which the solution can be evaluated

Returns: None

copy() → TspSolution[source]

Deep copy of the solution.

The copy() function should return a new object containing the same input as the current object, that respects the following expected behaviour: -y = x.copy() -if do some inplace change of y, the changes are not done in x.

Returns: a new object from which you can manipulate attributes without changing the original object.

end_index: int
lazy_copy() → TspSolution[source]

This function should return a new object but possibly with mutable attributes from the original objects.

A typical use of lazy copy is in evolutionary algorithms or genetic algorithm where the use of local move don’t need to do a possibly costly deepcopy.

Returns (Solution): copy (possibly shallow) of the Solution

length: float | None
lengths: list[float] | None
permutation: list[int]
permutation_from0: list[int]
start_index: int
discrete_optimization.tsp.problem.build_evaluate_function(tsp_model: TspProblem) → Callable[[list[int]], tuple[list[float], float]][source]
discrete_optimization.tsp.problem.build_evaluate_function_matrix(tsp_model: DistanceMatrixTspProblem) → Callable[[list[int]], tuple[list[int], int]][source]
discrete_optimization.tsp.problem.build_evaluate_function_np(tsp_model: TspProblem) → Callable[[list[int]], tuple[ndarray[Any, dtype[float64]], float]][source]
discrete_optimization.tsp.problem.compute_length(solution: list[int], start_index: int, end_index: int, list_points: Sequence[Point2D], node_count: int, length_permutation: int) → tuple[list[float], float][source]
discrete_optimization.tsp.problem.compute_length_matrix(solution: list[int] | ndarray, start_index: int, end_index: int, distance_matrix: ndarray, node_count: int, length_permutation: int) → tuple[list[int], int][source]
discrete_optimization.tsp.problem.compute_length_np(solution: list[int], start_index: int, end_index: int, np_points: ndarray, node_count: int, length_permutation: int) → tuple[ndarray[Any, dtype[float64]], float][source]
discrete_optimization.tsp.problem.length(point1: Point2D, point2: Point2D) → float[source]

discrete_optimization.tsp.solvers_map module

discrete_optimization.tsp.solvers_map.look_for_solver(domain: TspProblem) → list[type[TspSolver]][source]
discrete_optimization.tsp.solvers_map.look_for_solver_class(class_domain: type[TspProblem]) → list[type[TspSolver]][source]
discrete_optimization.tsp.solvers_map.return_solver(method: type[TspSolver], problem: TspProblem, **kwargs: Any) → TspSolver[source]
discrete_optimization.tsp.solvers_map.solve(method: type[TspSolver], problem: TspProblem, **kwargs: Any) → ResultStorage[source]

discrete_optimization.tsp.utils module

discrete_optimization.tsp.utils.baseline_in_order(nodeCount: int, points: Sequence[Point2D]) → tuple[Iterable[int], float, int][source]
discrete_optimization.tsp.utils.build_matrice_distance(nodeCount: int, method: Callable[[int, int], float]) → ndarray[Any, dtype[float64]][source]
discrete_optimization.tsp.utils.build_matrice_distance_np(nodeCount: int, points: Sequence[Point2D]) → tuple[ndarray, ndarray][source]
discrete_optimization.tsp.utils.closest_greedy(nodeCount: int, points: Sequence[Point2D]) → tuple[list[int], float, int][source]
discrete_optimization.tsp.utils.compute_length(solution: list[int], list_points: Sequence[Point2D], nodeCount: int) → tuple[list[float], float][source]
discrete_optimization.tsp.utils.length_1(point1: Point2D, point2: Point2D) → float[source]

Module contents