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: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OptalCpSolver

Solver for TSPTW using the OptalCP Python API (if available)

init_model(scaling: float = 100.0, **kwargs: Any)

Builds the OptalCP model for the TSPTW problem.

problem: TSPTWProblem

retrieve_solution(result: cp.SolveResult) → Solution

Extracts the tour from the OptalCP solution and constructs a TSPTWSolution.

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