discrete_optimization.tsp package

Subpackages

Submodules

discrete_optimization.tsp.mutation module

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]

class discrete_optimization.tsp.mutation.SwapTspMutation(problem: TspProblem, attribute: str | None = None, **kwargs: Any)[source]

Bases: SingleAttributeMutation

attribute_type: PermutationTsp

attribute_type_cls: alias of PermutationTsp

mutate(solution: TspSolution) → tuple[TspSolution, LocalMove][source]

problem: Point2DTspProblem

class discrete_optimization.tsp.mutation.TwoOptIntersectionTspMutation(problem: Point2DTspProblem, attribute: str | None = None, 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: TwoOptTspMutation

mutate_and_compute_obj(solution: TspSolution) → tuple[TspSolution, LocalMove, dict[str, float]][source]

class discrete_optimization.tsp.mutation.TwoOptTspMutation(problem: Point2DTspProblem, attribute: str | None = None, test_all: bool = False, nb_test: int | None = None, return_only_improvement: bool = False, **kwargs: Any)[source]

Bases: SingleAttributeMutation

attribute_type: PermutationTsp

attribute_type_cls: alias of PermutationTsp

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(solution: TspSolution) → tuple[TspSolution, LocalMove][source]

mutate_and_compute_obj(solution: TspSolution) → tuple[TspSolution, LocalMove, dict[str, float]][source]

node_count: int

points: Sequence[Point2D]

problem: Point2DTspProblem

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[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.PermutationTsp(range: Collection[int])[source]

Bases: Permutation

Attribute type specific to TspSolution.

Useful to make mutation catalog map TspSolution attribute to specific mutations.

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_2d: Callable[[list[int]], tuple[Iterable[float], float]]

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: SchedulingProblem[int]

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(variable: 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.

abstractmethod evaluate_function(var_tsp: TspSolution) → tuple[Iterable[float], float][source]

abstractmethod evaluate_function_indexes(index_1: int, index_2: int) → float[source]

get_attribute_register() → EncodingRegister[source]

Returns how the Solution should be encoded.

Useful to find automatically available mutations for local search. Used by genetic algorithms Ga and Nsga.

This needs only to be implemented in child classes when GA or LS solvers are to be used.

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

get_dummy_solution() → TspSolution[source]

Create a trivial solution for the problem.

Should satisfy the problem ideally. Does not exist for all kind of problems.

get_makespan_upper_bound() → int[source]: Get an upper bound on global makespan.

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.

is_optional(task: Task) → bool[source]

Whether a task is optional or not.

It means that the task can be ignored in the solution. If absent of the solution, it can also be removed from the constraints.

Default to no optional task.

list_points: Sequence[Point]

node_count: int

np_points: ndarray

satisfy(variable: 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.

property tasks_list: list[int]: List of all tasks to schedule or allocate to.

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: SchedulingSolution[int]

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. It should be implemented in child classes when caching subresults depending on the problem.

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

get_end_time(task: int) → int[source]

Get end time of the task

Hypothesis:: The returned time can have AbsentValue.ABSENT only if self.is_present(task) is False.

Parameters:: task

Returns:

get_start_time(task: int) → int[source]

Get start time of the task

Hypothesis:: The returned time can have AbsentValue.ABSENT only if self.is_present(task) is False.

Parameters:: task

Returns:

is_present(task: Task) → bool[source]

Tell whether the task is present in the solution.

It can mean several thing: - scheduling problem: start and end of the task are defined - allocation problem: a ressource has been allocated to the task - multimode: a mode has been chosen for the task - or a mix of it

Sometimes a scheduling allocation problem will allow no resource allocation for present task, it has to be defined problem by problem.

For convenience, a default implementation is provided which assumes that all tasks are present. To be overriden in subclasses.

If and only if this method returns False, the mode, start, and end of the task can have the value AbsentValue.ABSENT.

If the method returns False, the task is removed from all constraints during checks.

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]

problem: TspProblem

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[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[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[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]