discrete_optimization.tsp package

Subpackages

• discrete_optimization.tsp.mutation package
  • Submodules
  • discrete_optimization.tsp.mutation.mutation_tsp module
    • Mutation2Opt
      • Mutation2Opt.build()
      • Mutation2Opt.get_points()
      • Mutation2Opt.get_points_index()
      • Mutation2Opt.mutate()
      • Mutation2Opt.mutate_and_compute_obj()
      • Mutation2Opt.node_count
      • Mutation2Opt.points
    • Mutation2OptIntersection
      • Mutation2OptIntersection.build()
      • Mutation2OptIntersection.mutate_and_compute_obj()
      • Mutation2OptIntersection.nodeCount
      • Mutation2OptIntersection.points
    • MutationSwapTSP
      • MutationSwapTSP.build()
      • MutationSwapTSP.mutate()
      • MutationSwapTSP.mutate_and_compute_obj()
    • SwapTSPMove
      • SwapTSPMove.apply_local_move()
      • SwapTSPMove.backtrack_local_move()
    • ccw()
    • find_intersection()
    • get_points_index()
    • intersect()
  • Module contents
• discrete_optimization.tsp.solver package
  • Submodules
  • discrete_optimization.tsp.solver.solver_lp_iterative module
    • LP_TSP_Iterative
      • LP_TSP_Iterative.init_model()
      • LP_TSP_Iterative.init_model_cbc()
      • LP_TSP_Iterative.init_model_gurobi()
      • LP_TSP_Iterative.plot_solve()
      • LP_TSP_Iterative.retrieve_results_cbc()
      • LP_TSP_Iterative.retrieve_results_gurobi()
      • LP_TSP_Iterative.solve()
    • MILPSolver
      • MILPSolver.CBC
      • MILPSolver.GUROBI
    • build_graph_complete()
    • build_graph_pruned()
    • build_the_cycles()
    • rebuild_tsp_routine()
  • discrete_optimization.tsp.solver.solver_ortools module
    • TSP_ORtools
      • TSP_ORtools.init_model()
      • TSP_ORtools.solve()
  • discrete_optimization.tsp.solver.tsp_cp_solver module
    • TSP_CPModel
      • TSP_CPModel.FLOAT_VERSION
      • TSP_CPModel.INT_VERSION
    • TSP_CP_Solver
      • TSP_CP_Solver.init_model()
      • TSP_CP_Solver.retrieve_solution()
  • discrete_optimization.tsp.solver.tsp_solver module
    • SolverTSP
      • SolverTSP.problem
  • Module contents

Submodules

discrete_optimization.tsp.common_tools_tsp module

discrete_optimization.tsp.common_tools_tsp.baseline_in_order(nodeCount: int, points: Sequence[Point2D]) → Tuple[Iterable[int], float, int]

discrete_optimization.tsp.common_tools_tsp.build_matrice_distance(nodeCount: int, method: Callable[[int, int], float]) → ndarray[Any, dtype[float64]]

discrete_optimization.tsp.common_tools_tsp.build_matrice_distance_np(nodeCount: int, points: Sequence[Point2D]) → Tuple[ndarray, ndarray]

discrete_optimization.tsp.common_tools_tsp.closest_greedy(nodeCount: int, points: Sequence[Point2D]) → Tuple[List[int], float, int]

discrete_optimization.tsp.common_tools_tsp.compute_length(solution: List[int], list_points: Sequence[Point2D], nodeCount: int) → Tuple[List[float], float]

discrete_optimization.tsp.common_tools_tsp.length_1(point1: Point2D, point2: Point2D) → float

discrete_optimization.tsp.tsp_model module

class discrete_optimization.tsp.tsp_model.Point

Bases: object

class discrete_optimization.tsp.tsp_model.Point2D(x: float, y: float)

Bases: Point

x: float

y: float

class discrete_optimization.tsp.tsp_model.SolutionTSP(problem: TSPModel, 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)

Bases: Solution

change_problem(new_problem: Problem) → None

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() → SolutionTSP

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() → SolutionTSP

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

class discrete_optimization.tsp.tsp_model.TSPModel(list_points: Sequence[Point], node_count: int, start_index: int = 0, end_index: int = 0)

Bases: Problem

convert_original_perm_to_perm_from0(perm: Iterable[int]) → List[int]

convert_perm_from0_to_original_perm(perm_from0: Iterable[int]) → List[int]

evaluate(var_tsp: SolutionTSP) → Dict[str, float]

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]

abstract evaluate_function(var_tsp: SolutionTSP) → Tuple[Iterable[float], float]

abstract evaluate_function_indexes(index_1: int, index_2: int) → float

get_attribute_register() → EncodingRegister

Returns how the Solution should be encoded.

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

get_dummy_solution() → SolutionTSP

get_objective_register() → ObjectiveRegister

Returns the objective definition.

Returns (ObjectiveRegister): object defining the objective criteria.

get_random_dummy_solution() → SolutionTSP

get_solution_type() → Type[Solution]

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: SolutionTSP) → bool

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.tsp_model.TSPModel2D(list_points: Sequence[Point2D], node_count: int, start_index: int = 0, end_index: int = 0, use_numba: bool = True)

Bases: TSPModel

evaluate_function(var_tsp: SolutionTSP) → Tuple[Iterable[float], float]

evaluate_function_indexes(index_1: int, index_2: int) → float

list_points: Sequence[Point2D]

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

Bases: TSPModel

evaluate_function(var_tsp: SolutionTSP) → Tuple[List[int], int]

evaluate_function_indexes(index_1: int, index_2: int) → float

discrete_optimization.tsp.tsp_model.build_evaluate_function(tsp_model: TSPModel) → Callable[[List[int]], Tuple[List[float], float]]

discrete_optimization.tsp.tsp_model.build_evaluate_function_matrix(tsp_model: TSPModelDistanceMatrix) → Callable[[List[int]], Tuple[List[int], int]]

discrete_optimization.tsp.tsp_model.build_evaluate_function_np(tsp_model: TSPModel) → Callable[[List[int]], Tuple[ndarray[Any, dtype[float64]], float]]

discrete_optimization.tsp.tsp_model.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]

discrete_optimization.tsp.tsp_model.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]

discrete_optimization.tsp.tsp_model.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]

discrete_optimization.tsp.tsp_model.length(point1: Point2D, point2: Point2D) → float

discrete_optimization.tsp.tsp_parser module

discrete_optimization.tsp.tsp_parser.get_data_available(data_folder: str | None = None, data_home: str | None = None) → List[str]

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.tsp_parser.parse_file(file_path: str, start_index: int = 0, end_index: int = 0) → TSPModel2D

discrete_optimization.tsp.tsp_parser.parse_input_data(input_data: str, start_index: int = 0, end_index: int = 0) → TSPModel2D

discrete_optimization.tsp.tsp_solvers module

discrete_optimization.tsp.tsp_solvers.look_for_solver(domain: TSPModel) → List[Type[SolverTSP]]

discrete_optimization.tsp.tsp_solvers.look_for_solver_class(class_domain: Type[TSPModel]) → List[Type[SolverTSP]]

discrete_optimization.tsp.tsp_solvers.return_solver(method: Type[SolverTSP], problem: TSPModel, **kwargs: Any) → SolverTSP

discrete_optimization.tsp.tsp_solvers.solve(method: Type[SolverTSP], problem: TSPModel, **kwargs: Any) → ResultStorage

Module contents