discrete_optimization.gpdp.solvers package

Submodules

discrete_optimization.gpdp.solvers.gpdp_solver module

class discrete_optimization.gpdp.solvers.gpdp_solver.GpdpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

problem: GpdpProblem

discrete_optimization.gpdp.solvers.lp_iterative module

class discrete_optimization.gpdp.solvers.lp_iterative.BaseLinearFlowGpdpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: MilpSolver, GpdpSolver

add_order_constraints(nodes: Iterable[Hashable], lazy: bool = False) → None

convert_temporaryresults(temporary_results: list[TemporaryResult]) → list[tuple[Solution, float | TupleFitness]]

convert_to_variable_values(solution: Solution) → dict[gurobipy.Var, float]

Not used here by set_warm_start().

Parameters:

solution

Returns:

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

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

init_order_variables() → None

lazy: bool = False

Flag to know if contraints are added via a callback in a lazy way.

Should only be True in GurobiLazyConstraintLinearFlowGpdpSolver.

one_visit_per_clusters(nodes_of_interest: Iterable[Hashable], variables_edges: dict[int, dict[tuple[Hashable, Hashable], Any]]) → None

one_visit_per_node(nodes_of_interest: Iterable[Hashable], variables_edges: dict[int, dict[tuple[Hashable, Hashable], Any]]) → None

problem: GpdpProblem

resources_constraint(variables_edges: dict[int, dict[tuple[Hashable, Hashable], Any]]) → dict[str, dict[str, dict[Hashable, Any]]]

retrieve_current_solution(get_var_value_for_current_solution: Callable[[Any], float], get_obj_value_for_current_solution: Callable[[], float]) → GpdpSolution

Not used here as solve() is overriden

retrieve_current_temporaryresult(get_var_value_for_current_solution: Callable[[Any], float], get_obj_value_for_current_solution: Callable[[], float]) → TemporaryResult

set_warm_start(solution: GpdpSolution) → None

Make the solver warm start from the given solution.

Will be ignored if arg warm_start is not None in call to solve().

simple_capacity_constraint(variables_edges: dict[int, dict[tuple[Hashable, Hashable], Any]]) → dict[str, dict[int, dict[str, Any]]]

solve(parameters_milp: ParametersMilp | None = None, time_limit_subsolver: float | None = 30.0, do_lns: bool = True, nb_iteration_max: int = 10, json_dump_folder: str | None = None, warm_start: dict[Any, Any] | None = None, 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

solve_iterative(parameters_milp: ParametersMilp | None = None, time_limit_subsolver: float | None = 30.0, do_lns: bool = True, nb_iteration_max: int = 10, json_dump_folder: str | None = None, warm_start: dict[Any, Any] | None = None, callbacks: list[Callback] | None = None, **kwargs: Any) → ResultStorage

Parameters:

• parameters_milp

• time_limit_subsolver – the solve process of the LP subsolver stops after this time limit (in seconds). If None, no time limit is applied.

• do_lns

• nb_iteration_max

• json_dump_folder – if not None, solution will be dumped in this folder at each iteration

• warm_start

• **kwargs

Returns:

abstract solve_one_iteration(parameters_milp: ParametersMilp | None = None, time_limit: float | None = 30.0, **kwargs: Any) → list[TemporaryResult]

time_evolution(variables_edges: dict[int, dict[tuple[Hashable, Hashable], Any]]) → dict[str, dict[Hashable, Any]]

warm_start: GpdpSolution | None = None

class discrete_optimization.gpdp.solvers.lp_iterative.ConstraintHandlerOrWarmStart(linear_solver: BaseLinearFlowGpdpSolver, problem: GpdpProblem, do_lns: bool = True)

Bases: object

adding_constraint(rebuilt_dict: dict[int, list[Hashable]]) → None

class discrete_optimization.gpdp.solvers.lp_iterative.GurobiLazyConstraintLinearFlowGpdpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: GurobiLinearFlowGpdpSolver

lazy: bool = True

Flag to know if contraints are added via a callback in a lazy way.

Should only be True in GurobiLazyConstraintLinearFlowGpdpSolver.

retrieve_ith_temporaryresult(i: int) → TemporaryResult

solve_one_iteration(parameters_milp: ParametersMilp | None = None, time_limit: float | None = 30.0, **kwargs: Any) → list[TemporaryResult]

class discrete_optimization.gpdp.solvers.lp_iterative.GurobiLinearFlowGpdpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: GurobiMilpSolver, BaseLinearFlowGpdpSolver

convert_to_variable_values(solution: Solution) → dict[gurobipy.Var, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start().

Override it in subclasses to have a proper warm start. You can also override set_warm_start() if default behaviour is not sufficient.

init_model(**kwargs)

Initialize internal model used to solve.

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

model: 'gurobipy.Model' | None = None

set_warm_start(solution: GpdpSolution) → None

Make the solver warm start from the given solution.

By default, this is using convert_to_variable_values(). If not sufficient, you can override it. (And for instance make implementation of convert_to_variable_values() raise a NotImplementedError.)

solve(parameters_milp: ParametersMilp | None = None, time_limit_subsolver: float | None = 30.0, do_lns: bool = True, nb_iteration_max: int = 10, json_dump_folder: str | None = None, warm_start: dict[Any, Any] | None = None, 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

solve_one_iteration(parameters_milp: ParametersMilp | None = None, time_limit: float | None = 30.0, **kwargs: Any) → list[TemporaryResult]

class discrete_optimization.gpdp.solvers.lp_iterative.MathOptLinearFlowGpdpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OrtoolsMathOptMilpSolver, BaseLinearFlowGpdpSolver

convert_to_variable_values(solution: Solution) → dict[Variable, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start() to provide a suitable SolutionHint.variable_values. See https://or-tools.github.io/docs/pdoc/ortools/math_opt/python/model_parameters.html#SolutionHint for more information.

Override it in subclasses to have a proper warm start.

set_warm_start(solution: GpdpSolution) → None

Make the solver warm start from the given solution.

solve(parameters_milp: ParametersMilp | None = None, time_limit_subsolver: float | None = 30.0, do_lns: bool = True, nb_iteration_max: int = 10, json_dump_folder: str | None = None, warm_start: dict[Any, Any] | None = None, callbacks: list[Callback] | None = None, **kwargs: Any) → ResultStorage

Solve with OR-Tools MathOpt API

Parameters:

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

• parameters_milp – parameters passed to the MILP solver

• mathopt_solver_type – underlying solver type to use. Passed as solver_type to mathopt.solve()

• time_limit – the solve process stops after this time limit (in seconds). If None, no time limit is applied.

• mathopt_enable_output – turn on mathopt logging

• mathopt_model_parameters – passed to mathopt.solve() as model_params

• mathopt_additional_solve_parameters – passed to mathopt.solve() as params, except that parameters defined by above time_limit and parameters_milp will be overriden by them.

• **kwargs – passed to init_model() if model not yet existing

Returns:

solve_one_iteration(parameters_milp: ParametersMilp | None = None, time_limit: float | None = 30.0, mathopt_solver_type: SolverType = SolverType.CP_SAT, mathopt_enable_output: bool = False, mathopt_model_parameters: ModelSolveParameters | None = None, mathopt_additional_solve_parameters: SolveParameters | None = None, **kwargs: Any) → list[TemporaryResult]

class discrete_optimization.gpdp.solvers.lp_iterative.SubtourAddingConstraint(problem: GpdpProblem, linear_solver: BaseLinearFlowGpdpSolver, lazy: bool = False, cluster: bool = False, do_order: bool = False, consider_only_first_component: bool = True)

Bases: object

adding_component_constraints(list_solution: list[TemporaryResult]) → None

class discrete_optimization.gpdp.solvers.lp_iterative.TemporaryResult(flow_solution: dict[int, dict[tuple[Hashable, Hashable], int]], graph_merge: DiGraph, graph_vehicle: dict[int, DiGraph], obj: float, all_variables: dict[str, dict[Any, Any]] | None = None)

Bases: object

class discrete_optimization.gpdp.solvers.lp_iterative.TemporaryResultGurobiCallback(do_solver: GurobiLinearFlowGpdpSolver)

Bases: GurobiCallback

class discrete_optimization.gpdp.solvers.lp_iterative.TemporaryResultMathOptCallback(do_solver: MathOptLinearFlowGpdpSolver)

Bases: MathOptCallback

discrete_optimization.gpdp.solvers.lp_iterative.build_graph_solution(results: dict[str, dict[Hashable, Any]], obj: float, graph: Graph) → TemporaryResult

discrete_optimization.gpdp.solvers.lp_iterative.build_graph_solutions(solutions: list[tuple[dict, float]], graph: Graph) → list[TemporaryResult]

discrete_optimization.gpdp.solvers.lp_iterative.build_path_from_vehicle_type_flow(result_from_retrieve: dict[str, dict[Hashable, Any]], problem: GpdpProblem) → dict[int, list[Hashable]]

discrete_optimization.gpdp.solvers.lp_iterative.build_the_cycles(flow_solution: dict[tuple[Hashable, Hashable], int], component: set[Hashable], start_index: Hashable, end_index: Hashable) → tuple[list[Hashable], dict[Hashable, int]]

discrete_optimization.gpdp.solvers.lp_iterative.construct_edges_in_out_dict(variables_edges: dict[int, dict[tuple[Hashable, Hashable], Any]], clusters_dict: dict[Hashable, Hashable]) → tuple[dict[Hashable, set[tuple[int, tuple[Hashable, Hashable]]]], dict[Hashable, set[tuple[int, tuple[Hashable, Hashable]]]], dict[int, dict[Hashable, set[tuple[Hashable, Hashable]]]], dict[int, dict[Hashable, set[tuple[Hashable, Hashable]]]], dict[Hashable, set[tuple[int, tuple[Hashable, Hashable]]]], dict[Hashable, set[tuple[int, tuple[Hashable, Hashable]]]], dict[int, dict[Hashable, set[tuple[Hashable, Hashable]]]], dict[int, dict[Hashable, set[tuple[Hashable, Hashable]]]]]

discrete_optimization.gpdp.solvers.lp_iterative.convert_temporaryresult_to_gpdpsolution(temporaryresult: TemporaryResult, problem: GpdpProblem) → GpdpSolution

discrete_optimization.gpdp.solvers.lp_iterative.rebuild_routine(sorted_connected_component: list[tuple[set[Hashable], int]], paths_component: dict[int, list[Hashable]], node_to_component: dict[Hashable, int], indexes: dict[int, dict[Hashable, int]], graph: DiGraph, edges: set[tuple[Hashable, Hashable]], evaluate_function_indexes: Callable[[Hashable, Hashable], float], start_index: Hashable, end_index: Hashable) → list[Hashable]

discrete_optimization.gpdp.solvers.lp_iterative.rebuild_routine_variant(sorted_connected_component: list[tuple[set[Hashable], int]], paths_component: dict[int, list[Hashable]], node_to_component: dict[Hashable, int], indexes: dict[int, dict[Hashable, int]], graph: DiGraph, edges: set[tuple[Hashable, Hashable]], evaluate_function_indexes: Callable[[Hashable, Hashable], float], start_index: Hashable, end_index: Hashable) → list[Hashable]

discrete_optimization.gpdp.solvers.lp_iterative.reevaluate_result(temporary_result: TemporaryResult, problem: GpdpProblem, variant_rebuilt: bool = True, possible_subcycle_in_component: bool = True) → TemporaryResult

discrete_optimization.gpdp.solvers.lp_iterative.retrieve_current_solution(get_var_value_for_current_solution: Callable[[Any], float], get_obj_value_for_current_solution: Callable[[], float], variable_decisions: dict[str, Any]) → tuple[dict[str, dict[Hashable, Any]], float]

discrete_optimization.gpdp.solvers.lp_iterative.update_model_generic(problem: GpdpProblem, lp_solver: BaseLinearFlowGpdpSolver, components_global: list[tuple[set[Hashable], int]], edges_in_all_vehicles: dict[Hashable, set[tuple[int, tuple[Hashable, Hashable]]]], edges_out_all_vehicles: dict[Hashable, set[tuple[int, tuple[Hashable, Hashable]]]], lazy: bool = False, cluster: bool = False, consider_only_first_component: bool = True, do_order: bool = False) → list[Any]

discrete_optimization.gpdp.solvers.ortools_routing module

class discrete_optimization.gpdp.solvers.ortools_routing.FirstSolutionStrategy(value)

Bases: Enum

Enumeration of first solution strategies.

Extracted from ortools Enum-like class. https://developers.google.com/optimization/routing/routing_options#first_solution_strategy

ALL_UNPERFORMED = 6

AUTOMATIC = 15

BEST_INSERTION = 7

CHRISTOFIDES = 13

EVALUATOR_STRATEGY = 5

FIRST_UNBOUND_MIN_VALUE = 12

GLOBAL_CHEAPEST_ARC = 1

LOCAL_CHEAPEST_ARC = 2

LOCAL_CHEAPEST_COST_INSERTION = 16

LOCAL_CHEAPEST_INSERTION = 9

PARALLEL_CHEAPEST_INSERTION = 8

PATH_CHEAPEST_ARC = 3

PATH_MOST_CONSTRAINED_ARC = 4

SAVINGS = 10

SEQUENTIAL_CHEAPEST_INSERTION = 14

SWEEP = 11

UNSET = 0

class discrete_optimization.gpdp.solvers.ortools_routing.LocalSearchMetaheuristic(value)

Bases: Enum

Enumeration of local search meta-heuristic.

Extracted from ortools Enum-like class. https://developers.google.com/optimization/routing/routing_options#local_search_options

AUTOMATIC = 6

GENERIC_TABU_SEARCH = 5

GREEDY_DESCENT = 1

GUIDED_LOCAL_SEARCH = 2

SIMULATED_ANNEALING = 3

TABU_SEARCH = 4

UNSET = 0

class discrete_optimization.gpdp.solvers.ortools_routing.NodePosition(value)

Bases: Enum

Node position inside a trajectory.

Useful e.g. to distinguish between the starting node and ending node when the trajectory is a loop.

END = 'end'

INTERMEDIATE = 'intermediate'

START = 'start'

class discrete_optimization.gpdp.solvers.ortools_routing.OrtoolsGpdpSolver(problem: GpdpProblem, factor_multiplier_distance: float = 1, factor_multiplier_time: float = 1, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: GpdpSolver, WarmstartMixin

build_search_parameters(**kwargs: Any) → RoutingSearchParameters

hyperparameters: list[Hyperparameter] = [EnumHyperparameter(name='first_solution_strategy', default=<FirstSolutionStrategy.SAVINGS: 10>, depends_on=None, name_in_kwargs='first_solution_strategy'), EnumHyperparameter(name='local_search_metaheuristic', default=<LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH: 2>, depends_on=None, name_in_kwargs='local_search_metaheuristic'), CategoricalHyperparameter(name='use_lns', default=True, depends_on=None, name_in_kwargs='use_lns'), CategoricalHyperparameter(name='use_cp', default=True, depends_on=None, name_in_kwargs='use_cp'), CategoricalHyperparameter(name='use_cp_sat', default=False, depends_on=None, name_in_kwargs='use_cp_sat')]

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.

initial_solution: GpdpSolution | None = None

Initial solution used for warm start.

problem: GpdpProblem

set_warm_start(solution: GpdpSolution) → None

Make the solver warm start from the given solution.

Will be ignored if arg init_solution, is not None in call to solve().

solve(search_parameters: RoutingSearchParameters | None = None, 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

class discrete_optimization.gpdp.solvers.ortools_routing.ParametersCost(dimension_name: str, global_span: bool = True, sum_over_vehicles: bool = False, coefficient_vehicles: float | list[float] = 100)

Bases: object

static default() → ParametersCost

class discrete_optimization.gpdp.solvers.ortools_routing.RoutingMonitor(do_solver: OrtoolsGpdpSolver, callback: Callback)

Bases: SearchMonitor

AtSolution() → bool

This method is called when a valid solution is found. If the return value is true, then search will resume after. If the result is false, then search will stop there.

EnterSearch()

Beginning of the search.

ExitSearch()

End of the search.

retrieve_current_solution() → None

discrete_optimization.gpdp.solvers.ortools_routing.apply_cost(list_parameters_cost: list[ParametersCost], routing: RoutingModel) → None

discrete_optimization.gpdp.solvers.ortools_routing.convert_to_gpdpsolution(problem: GpdpProblem, sol: tuple[dict[int, list[int]], dict[tuple[int, int, NodePosition], dict[str, tuple[float, float, float]]], float, float, float]) → GpdpSolution

discrete_optimization.gpdp.solvers.ortools_routing.status_description = {0: 'ROUTING_NOT_SOLVED', 1: 'ROUTING_SUCCESS', 2: 'ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED', 3: 'ROUTING_FAIL', 4: 'ROUTING_FAIL_TIMEOUT', 5: 'ROUTING_INVALID', 6: 'ROUTING_INFEASIBLE', 7: 'ROUTING_OPTIMAL'}

Mapping from status integer to description string.

This maps the integer returned by routing_model.status to the corresponding string.

We use the attributes of RoutingModel to construct the dictionary. https://developers.google.com/optimization/routing/routing_options#search_status

Module contents