discrete_optimization.tsptw.solvers package

Submodules

discrete_optimization.tsptw.solvers.cpsat module

class discrete_optimization.tsptw.solvers.cpsat.CpSatTSPTWSolver(problem: TSPTWProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: OrtoolsCpSatSolver, WarmstartMixin

CP-SAT solver for the Traveling Salesman Problem with Time Windows.

This solver uses a circuit constraint to ensure a valid tour and enforces time window constraints through implications based on the selected arcs.

problem

The TSP-TW problem instance.

Type:

TSPTWProblem

variables

A dictionary to store the CP-SAT model variables, including arc variables (‘x_arc’), time variables (‘t_time’), and the makespan variable.

Type:

Dict[str, Any]

init_model(scaling_factor: float = 10.0, relaxed: bool = False, **kwargs: Any) → None

Initialise the CP-SAT model.

problem: TSPTWProblem

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → TSPTWSolution

Build a TSPTWSolution from the CP-SAT solver’s callback.

Parameters:

cpsolvercb – The ortools callback object containing the current solution.

Returns:

The current solution in the TSPTWSolution format.

set_warm_start(solution: TSPTWSolution) → None

Provides a warm start hint to the CP-SAT solver from an existing solution.

Parameters:

solution – A TSPTWSolution object.

discrete_optimization.tsptw.solvers.dp module

class discrete_optimization.tsptw.solvers.dp.DpTspTwSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: DpSolver

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='add_dominated_transition', default=False, depends_on=None, name_in_kwargs='add_dominated_transition')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

problem: TSPTWProblem

retrieve_solution(sol: Solution) → TSPTWSolution

transitions: dict

discrete_optimization.tsptw.solvers.optal module

class discrete_optimization.tsptw.solvers.optal.OptalTspTwSolver(problem: TSPTWProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OptalSolver

build_command(parameters_cp: ParametersCp | None = None, time_limit: int = 10, **args: Any)

Build the command line call for optal cp. You can pass parameters from the Parameters class of optal cp for example : searchType=fds, worker0-1.noOverlapPropagationLevel=4 if you want worker 0 and 1 to use this parameters etc. TODO : list such parameters in hyperparameter of this wrapped solver.

init_model(scaling: float = 100.0, **args: Any) → None

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

problem: TSPTWProblem

retrieve_current_solution(dict_results: dict) → TSPTWSolution

discrete_optimization.tsptw.solvers.optal.tsptw_to_dict(problem: TSPTWProblem, scaling: float = 100)

Exports the TSP problem to a JSON file, computing and storing the full distance matrix.

discrete_optimization.tsptw.solvers.ortools_routing module

class discrete_optimization.tsptw.solvers.ortools_routing.OrtoolsTspTwSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

gpdp_problem: GpdpProblem

init_model(time_limit=10, scaling: float = 100, **kwargs: Any) → None

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

problem: TSPTWProblem

solve(callbacks: list[Callback] | None = None, **kwargs: Any) → ResultStorage

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

solver: OrtoolsGpdpSolver

Module contents