discrete_optimization.generic_tools package

Subpackages

Submodules

discrete_optimization.generic_tools.asp_tools module

class discrete_optimization.generic_tools.asp_tools.ASPCallback(do_solver: ASPClingoSolver, callback: Callback, dump_model_in_folders: bool = False)[source]

Bases: object

on_model(model: Model) → bool[source]
class discrete_optimization.generic_tools.asp_tools.ASPClingoSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverDO

Base class for solver based on Answer Set Programming formulation and clingo solver.

ctl: Control | None = None
early_stopping_exception: Exception | None = None
abstract retrieve_solution(model: Model) → Solution[source]

Construct a do solution from a clingo model.

Parameters:

model – the current constructed clingo model

Returns:

the intermediate solution, at do format.

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

Solve the problem with a CPSat solver drom ortools library.

Parameters:

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

  • **kwargs – keyword arguments passed to self.init_model()

Returns:

A dedicated clingo callback is used to: - update a resultstorage each time a new solution is found by the clingo solver. - call the user (do) callbacks at each new solution, with the possibility of early stopping if the callback return True.

This clingo callback use the method self.retrieve_solution() to reconstruct a do Solution from the current clingo model.

discrete_optimization.generic_tools.cp_tools module

Constraint programming common utilities and class that should be used by any solver using CP

class discrete_optimization.generic_tools.cp_tools.CPSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverDO

Additional function to be implemented by a CP Solver.

get_status_solver() → StatusSolver | None[source]
abstract init_model(**args: Any) → None[source]

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

abstract solve(callbacks: List[Callback] | None = None, parameters_cp: ParametersCP | None = None, **args: Any) → ResultStorage[source]

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

status_solver: StatusSolver | None = None
class discrete_optimization.generic_tools.cp_tools.CPSolverName(value)[source]

Bases: Enum

Enum choice of underlying CP/LP solver used by Minizinc typically

CHUFFED = 0
CPLEX = 2
CPOPT = 3
GECODE = 1
GUROBI = 4
HIGHS = 6
ORTOOLS = 5
class discrete_optimization.generic_tools.cp_tools.MinizincCPSolution(_output_item: str | None = None, **kwargs: Any)[source]

Bases: object

Base class used by minizinc when building a new solution.

This is used as an entry point for callbacks. It is actually a child class dynamically created during solve that will be used by minizinc, with appropriate callbacks, resultstorage and reference to the solver.

callback: Callback

User-definied callback to be called at each step.

static generate_subclass_for_solve(solver: MinizincCPSolver, callback: Callback) → Type[MinizincCPSolution][source]

Generate dynamically a subclass with initialized class attributes.

Parameters:

  • solver

  • callback

Returns:

res: ResultStorage

ResultStorage in which the solution will be added, class attribute.

solution: Solution

Solution wrapped.

solver: MinizincCPSolver

Instance of the solver using this class as an output_type.

step: int

Step number, updated as a class attribute.

class discrete_optimization.generic_tools.cp_tools.MinizincCPSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: CPSolver

CP solver wrapping a minizinc solver.

hyperparameters: List[Hyperparameter] = [EnumHyperparameter(name='cp_solver_name', default=<CPSolverName.CHUFFED: 0>, choices=[<CPSolverName.CHUFFED: 0>, <CPSolverName.GECODE: 1>, <CPSolverName.CPLEX: 2>, <CPSolverName.CPOPT: 3>, <CPSolverName.GUROBI: 4>, <CPSolverName.ORTOOLS: 5>, <CPSolverName.HIGHS: 6>])]

Hyperparameters available for this solver.

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

  • __init__()

  • init_model() (when available)

  • solve()

instance: Instance | None = None
abstract retrieve_solution(_output_item: str | None = None, **kwargs: Any) → Solution[source]

Return a d-o solution from the variables computed by minizinc.

Parameters:

  • _output_item – string representing the minizinc solver output passed by minizinc to the solution constructor

  • **kwargs – keyword arguments passed by minzinc to the solution contructor containing the objective value (key “objective”), and the computed variables as defined in minizinc model.

Returns:

silent_solve_error: bool = False

If True and solve should raise an error, a warning is raised instead and an empty ResultStorage returned.

solve(callbacks: List[Callback] | None = None, parameters_cp: ParametersCP | None = None, instance: Instance | None = None, **kwargs: Any) → ResultStorage[source]

Solve the CP problem with minizinc

Parameters:

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

  • parameters_cp – parameters specific to CP solvers

  • instance – if specified, use this minizinc instance (and underlying model) rather than self.instance Useful in iterative solvers like LNS_CP.

  • **kwargs – any argument specific to the solver

Returns:

class discrete_optimization.generic_tools.cp_tools.ParametersCP(time_limit: int, intermediate_solution: bool, all_solutions: bool, nr_solutions: int, time_limit_iter0: int | None = None, free_search: bool = False, multiprocess: bool = False, nb_process: int = 1, optimisation_level: int = 1)[source]

Bases: object

Parameters that can be used by any cp - solver

all_solutions: bool
copy() → ParametersCP[source]
static default() → ParametersCP[source]
static default_cpsat() → ParametersCP[source]
static default_fast_lns() → ParametersCP[source]
static default_free() → ParametersCP[source]
intermediate_solution: bool
multiprocess: bool
nb_process: int
nr_solutions: int
optimisation_level: int
time_limit: int
time_limit_iter0: int
class discrete_optimization.generic_tools.cp_tools.SignEnum(value)[source]

Bases: Enum

An enumeration.

EQUAL = '=='
LEQ = '<='
LESS = '<'
UEQ = '>='
UP = '>'
class discrete_optimization.generic_tools.cp_tools.StatusSolver(value)[source]

Bases: Enum

An enumeration.

OPTIMAL = 'OPTIMAL'
SATISFIED = 'SATISFIED'
UNKNOWN = 'UNKNOWN'
UNSATISFIABLE = 'UNSATISFIABLE'
discrete_optimization.generic_tools.cp_tools.find_right_minizinc_solver_name(cp_solver_name: CPSolverName)[source]

This small utility function is adapting the ortools tag if needed. :param cp_solver_name: desired cp solver backend :return: the tag for minizinc corresponding to the given cpsolver.

discrete_optimization.generic_tools.do_mutation module

class discrete_optimization.generic_tools.do_mutation.LocalMove[source]

Bases: object

abstract apply_local_move(solution: Solution) → Solution[source]
abstract backtrack_local_move(solution: Solution) → Solution[source]
class discrete_optimization.generic_tools.do_mutation.LocalMoveDefault(prev_solution: Solution, new_solution: Solution)[source]

Bases: LocalMove

Not clever local move If you’re lazy or don’t have the choice, don’t do in place modification of the previous solution, so that you can retrieve it directly. So the backward operator is then obvious.

apply_local_move(solution: Solution) → Solution[source]
backtrack_local_move(solution: Solution) → Solution[source]
class discrete_optimization.generic_tools.do_mutation.Mutation[source]

Bases: object

static build(problem: Problem, solution: Solution, **kwargs: Any) → Mutation[source]
abstract mutate(solution: Solution) → Tuple[Solution, LocalMove][source]
abstract mutate_and_compute_obj(solution: Solution) → Tuple[Solution, LocalMove, Dict[str, float]][source]

discrete_optimization.generic_tools.do_problem module

Base module for the problem implementation in discrete-optimization library.

class discrete_optimization.generic_tools.do_problem.BaseMethodAggregating(value)[source]

Bases: Enum

Enum class used to specify how an evaluation of a multiscenario problem should be aggregated.

MAX = 5

Take the max value over the scenarios

MEAN = 0

averaging over scenarios

MEDIAN = 1

taking the median over scenarios

MIN = 4

Take the min value over the scenarios

PERCENTILE = 2

take a given percentile over scenario (the percentile value is given as additional parameter in MethodAggregating object

PONDERATION = 3

ponderate the different scenario with different weights. (MEAN would be equivalent with equal ponderation for example)

class discrete_optimization.generic_tools.do_problem.EncodingRegister(dict_attribute_to_type: Dict[str, Any])[source]

Bases: object

Placeholder class where the Solution definition is defined.

dict_attribute_to_type

specifies the encoding of a solution object.

Type:

Dict[str, Any]

User may refer to example in the different implemented problem definition.

Examples

in ColoringModel, to specify the colors attribute of the Solution, you will do the following. dict_register = {

“colors”: {

“name”: “colors”, “type”: [TypeAttribute.LIST_INTEGER], “n”: self.number_of_nodes, “arrity”: self.number_of_nodes,

}

}

dict_attribute_to_type: Dict[str, Any]
get_types() → List[TypeAttribute][source]

Returns all the TypeAttribute that are present in our encoding.

lower_bound_vector_encoding(encoding_name: str) → List[int][source]

Return for an encoding that is of type LIST_INTEGER or associated, the lower bound vector. Examples: if the vector should contains value higher or equal to 1, the function will return a list full of 1.

upper_bound_vector_encoding(encoding_name: str) → List[int][source]

Return for an encoding that is of type LIST_INTEGER or associated, the upper bound vector. Examples: if the vector should contains value higher or equal to 1, the function will return a list full of 1.

class discrete_optimization.generic_tools.do_problem.MethodAggregating(base_method_aggregating: BaseMethodAggregating, percentile: float = 90.0, ponderation: ndarray | None = None)[source]

Bases: object

Specifies how the evaluation on a RobustProblem (i.e a multiscenario problem) should be aggregated in an objective criteria.

base_method_aggregating

the base method for aggregation of evaluation

Type:

BaseMethodAggregating

percentile

if base_method_aggregating==BaseMethodAggregating.PERCENTILE, then the percentile value used will be this one.

Type:

float

ponderation

if base_method_aggregating==BaseMethodAggregating.PONDERATION, then the ponderation value used will be this one. It should be the same size as the number of scenario in the RobustProblem

Type:

np.array

class discrete_optimization.generic_tools.do_problem.ModeOptim(value)[source]

Bases: Enum

Enum class to specify minimization or maximization problems.

MAXIMIZATION = 0
MINIMIZATION = 1
class discrete_optimization.generic_tools.do_problem.ObjectiveDoc(type: discrete_optimization.generic_tools.do_problem.TypeObjective, default_weight: float)[source]

Bases: object

default_weight: float
type: TypeObjective
class discrete_optimization.generic_tools.do_problem.ObjectiveHandling(value)[source]

Bases: Enum

Enum class specifying how should be built the objective criteria.

When SINGLE, it means the problem only returns one KPI to be minimize/maximize When AGGREGATE, the problems has several KPI to combine with different ponderations. When MULTI_OBJ, pareto optimisation will be done if possible.

AGGREGATE = 1
MULTI_OBJ = 2
SINGLE = 0
class discrete_optimization.generic_tools.do_problem.ObjectiveRegister(objective_sense: ModeOptim, objective_handling: ObjectiveHandling, dict_objective_to_doc: Dict[str, Any])[source]

Bases: object

Store all the specification concerning the objective criteria.

To specify the objective criteria, you’re invited to choose the objective_sense (ModeOptim), how the criteria is computed (ObjectiveHandling) and how are defined each KPI that are returned by the problem.evaluate() function.

Even though the dict_objective is not strictly typed, it should contain as key the same key as the problem.evaluate(sol) function as you see in the examples. As value the dictionnary contains a type of the corresponding KPI (one TypeObjective value), and a default weight of the KPI to take into account (for SINGLE, and AGGREGATE ObjectiveHandling). The weight should be coherent with the ModeOptim chosen.

Examples

In ColoringProblem implementation. dict_objective = {

“nb_colors”: ObjectiveDoc(type=TypeObjective.OBJECTIVE, default_weight=-1), “nb_violations”: ObjectiveDoc(type=TypeObjective.PENALTY, default_weight=-100),

}

Attributes

objective_sense (ModeOptim): min or max problem objective_handling (ObjectiveHandling): specify how the different kpi are transformed into an optimization criteria dict_objective_to_doc: for each kpi, gives their default weight and their TypeObjective.

dict_objective_to_doc: Dict[str, ObjectiveDoc]
get_list_objective_and_default_weight() → Tuple[List[str], List[float]][source]

Flatten the list of kpi names and default weight.

Returns: list of kpi names, list of default weight for the aggregated objective function.

objective_handling: ObjectiveHandling
objective_sense: ModeOptim
class discrete_optimization.generic_tools.do_problem.ParamsObjectiveFunction(objective_handling: ObjectiveHandling, objectives: List[str], weights: List[float], sense_function: ModeOptim)[source]

Bases: object

Alternative of Objective Register, but with the same idea of storing the objective handling, ponderation and sense of optimization.

This class has been implemented after ObjectiveRegister to be able to call solvers and use user choice optimization.

objective_handling: ObjectiveHandling
objectives: List[str]
sense_function: ModeOptim
weights: List[float]
class discrete_optimization.generic_tools.do_problem.Problem[source]

Bases: object

Base class for a discrete optimization problem.

abstract evaluate(variable: Solution) → 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.

evaluate_mobj(variable: Solution) → TupleFitness[source]

Default implementation of multiobjective evaluation.

It consists in flattening the evaluate() function and put in an array. User should probably custom this to be more efficient.

Parameters:

variable (Solution) – the Solution object to evaluate.

Returns (TupleFitness): a flattened tuple fitness object representing the multi-objective criteria.

evaluate_mobj_from_dict(dict_values: Dict[str, float]) → TupleFitness[source]

Return an multiobjective fitness from a dictionnary of kpi (output of evaluate function).

It consists in flattening the evaluate() function and put in an array. User should probably custom this to be more efficient.

Parameters:

dict_values – output of evaluate() function

Returns (TupleFitness): a flattened tuple fitness object representing the multi-objective criteria.

abstract get_attribute_register() → EncodingRegister[source]

Returns how the Solution should be encoded.

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

abstract get_objective_register() → ObjectiveRegister[source]

Returns the objective definition.

Returns (ObjectiveRegister): object defining the objective criteria.

get_optuna_study_direction() → str[source]

Convert the objective sense into the expected string by Optuna.

abstract get_solution_type() → Type[Solution][source]

Returns the class implementation of a Solution.

Returns (class): class object of the given Problem.

abstract satisfy(variable: Solution) → 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.

class discrete_optimization.generic_tools.do_problem.RobustProblem(list_problem: Sequence[Problem], method_aggregating: MethodAggregating)[source]

Bases: Problem

Problem built from a list of other problem (that should be considered as “scenario” optimisation problems).

list_problem

List of Problems corresponding to different scenarios.

method_aggregating

specifies how the evaluation on each scenario should be merged

aggregate_vector() → Callable[[_SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes]], float][source]

Returns the aggregation function coherent with the method_aggregating attribute.

Returns: aggregation function

evaluate(variable: Solution) → Dict[str, float][source]

Aggregated evaluate function.

Parameters:

variable (Solution) – Solution to evaluate on the different scenarios.

Returns (Dict[str,float]): aggregated kpi on different scenarios.

get_attribute_register() → EncodingRegister[source]

See `Problem.get_attribute_register` doc.

get_objective_register() → ObjectiveRegister[source]

See `Problem.get_objective_register` doc.

get_solution_type() → Type[Solution][source]

See `Problem.get_solution_type` doc.

satisfy(variable: Solution) → bool[source]

Computes if a solution satisfies or not the constraints of the problem.

Warning

For RobustProblem, we consider than checking the satisfiability on the first scenario is enough. It is not necessarly correct

Parameters:

variable – the Solution object to check satisfability

Returns (bool): boolean true if the constraints are fulfilled, false elsewhere.

class discrete_optimization.generic_tools.do_problem.Solution[source]

Bases: object

Base class for a solution to a Problem.

abstract 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.

Parameters:

new_problem (Problem) – another problem instance from which the solution can be evaluated

Returns: None

abstract copy() → Solution[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.

get_attribute_register(problem: Problem) → EncodingRegister[source]

Returns how the Solution is encoded for the Problem.

By default it returns the encoding register of the problem itself. However it can make sense that for the same Problem, you have different Solution class with different encoding.

Returns (EncodingRegister): content of the encoding of the Solution.

lazy_copy() → Solution[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

class discrete_optimization.generic_tools.do_problem.TypeAttribute(value)[source]

Bases: Enum

Enum class to specify how are defined the attributes of a Solution.

This specification will be particularly usefull if you want to give a try to local search algorithms, which will use the information to use the right local moves.

LIST_BOOLEAN = 1
LIST_BOOLEAN_KNAP = 6
LIST_FLOATS = 10
LIST_INTEGER = 0
LIST_INTEGER_SPECIFIC_ARITY = 7
PERMUTATION = 2
PERMUTATION_RCPSP = 4
PERMUTATION_TSP = 3
SET_INTEGER = 5
SET_TUPLE_INTEGER = 8
VRP_PATHS = 9
class discrete_optimization.generic_tools.do_problem.TypeObjective(value)[source]

Bases: Enum

Enum class to specify what should each KPI be.

OBJECTIVE = 0
PENALTY = 1
discrete_optimization.generic_tools.do_problem.build_aggreg_function_and_params_objective(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None) → Tuple[Callable[[Solution], float] | Callable[[Solution], TupleFitness], Callable[[Dict[str, float]], float] | Callable[[Dict[str, float]], TupleFitness], ParamsObjectiveFunction][source]

Build evaluation function from the problem and the params of objective function.

If params_objective_function is None then we compute inside this function the default ParamsObjectiveFunction.

Parameters:

  • problem – problem to build evaluation function from

  • params_objective_function – params of the objective function.

Returns: the function returns a 3-uple :

-first element is a function of Solution->Union[float,TupleFitness] -second element is a function of (Dict[str,float])->Union[float, TupleFitness] -third element, return the params_objective_function (either the object passed in argument of the function, or the one created inside the function.)

discrete_optimization.generic_tools.do_problem.build_evaluate_function_aggregated(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None) → Tuple[Callable[[Solution], float], Callable[[Dict[str, float]], float]] | Tuple[Callable[[Solution], TupleFitness], Callable[[Dict[str, float]], TupleFitness]][source]

Build 2 eval functions based from the problem and params of objective function.

The 2 eval function are callable with a Solution for the first one, and a Dict[str, float] (output of Problem.evaluate function) for the second one. Those two eval function will return either a scalar for monoobjective problem or a TupleFitness for multiobjective. those aggregated function will be the one actually called by an optimisation algorithm at the end.

Parameters:

  • problem (Problem) – problem to build the evaluation function s

  • params_objective_function (ParamsObjectiveFunction) – params of the objective function.

Returns: the function returns a 2-uple :

-first element is a function of Solution->Union[float,TupleFitness] -second element is a function of (Dict[str,float])->Union[float, TupleFitness]

discrete_optimization.generic_tools.do_problem.get_default_objective_setup(problem: Problem) → ParamsObjectiveFunction[source]

Build ParamsObjectiveFunction from the ObjectiveRegister returned by the problem.

Parameters:

problem (Problem) – problem to build objective setup

Returns: default ParamsObjectiveFunction of the problem.

discrete_optimization.generic_tools.do_problem.lower_bound_vector_encoding_from_dict(dict_encoding: Dict[str, Any]) → List[int][source]
discrete_optimization.generic_tools.do_problem.upper_bound_vector_encoding_from_dict(dict_encoding: Dict[str, Any]) → List[int][source]

Return for an encoding that is of type LIST_INTEGER or associated, the upper bound vector.

Examples: if the vector should contains value higher or equal to 1, the function will return a list full of 1.

discrete_optimization.generic_tools.do_solver module

Minimal API for a discrete-optimization solver.

class discrete_optimization.generic_tools.do_solver.SolverDO(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: Hyperparametrizable

Base class for a discrete-optimization solver.

init_model(**kwargs: Any) → None[source]

Initialize intern model used to solve.

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

problem: Problem
abstract solve(callbacks: List[Callback] | None = None, **kwargs: Any) → ResultStorage[source]

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

discrete_optimization.generic_tools.exceptions module

exception discrete_optimization.generic_tools.exceptions.SolveEarlyStop[source]

Bases: Exception

Exception used to stop some solvers

See for instance discrete_optimization.pickup_vrp.solver.ortools_solver.ORToolsGPDP.

discrete_optimization.generic_tools.ghh_tools module

class discrete_optimization.generic_tools.ghh_tools.SupportsDunderGT(*args, **kwargs)[source]

Bases: Protocol

class discrete_optimization.generic_tools.ghh_tools.SupportsDunderLT(*args, **kwargs)[source]

Bases: Protocol

discrete_optimization.generic_tools.ghh_tools.argsort(list_or_array: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes]) → ndarray[Any, dtype[int64]][source]

Return the sorted array with indexes

Parameters:

list_or_array – any list or array

Returns: indexes of array by increasing order.

discrete_optimization.generic_tools.ghh_tools.index_max(list_or_array: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes]) → int64[source]

Argmax operator that can be used in gp.

Parameters:

list_or_array – any list or array

Returns: index of maximum element of the array

discrete_optimization.generic_tools.ghh_tools.index_min(list_or_array: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes]) → int64[source]

Argmin operator that can be used in gp.

Parameters:

list_or_array – any list or array

Returns: index of minimum element of the array

discrete_optimization.generic_tools.ghh_tools.max_operator(left: SupportsRichComparisonT, right: SupportsRichComparisonT) → SupportsRichComparisonT[source]
discrete_optimization.generic_tools.ghh_tools.max_operator_list(list_: Iterable[SupportsRichComparisonT]) → SupportsRichComparisonT[source]
discrete_optimization.generic_tools.ghh_tools.min_operator(left: SupportsRichComparisonT, right: SupportsRichComparisonT) → SupportsRichComparisonT[source]
discrete_optimization.generic_tools.ghh_tools.min_operator_list(list_: Iterable[SupportsRichComparisonT]) → SupportsRichComparisonT[source]
discrete_optimization.generic_tools.ghh_tools.protected_div(left: float, right: float) → float[source]

discrete_optimization.generic_tools.graph_api module

class discrete_optimization.generic_tools.graph_api.Graph(nodes: List[Tuple[Hashable, Dict[str, Any]]], edges: List[Tuple[Hashable, Hashable, Dict[str, Any]]], undirected: bool = True, compute_predecessors: bool = True)[source]

Bases: object

ancestors_map() → Dict[Hashable, Set[Hashable]][source]
build_edges() → None[source]
build_nodes_infos_dict() → None[source]
check_loop() → List[Tuple[Hashable, Hashable, str]] | None[source]
compute_all_shortest_path(attribute_name: str | None = None) → Dict[Hashable, Dict[Hashable, Tuple[List[Hashable], float]]][source]
compute_length(path: List[Hashable], attribute_name: str | None = None)[source]
compute_shortest_path(source: Hashable, target: Hashable, attribute_name: str | None = None)[source]
descendants_map() → Dict[Hashable, Set[Hashable]][source]
get_attr_edge(node1: Hashable, node2: Hashable, attr: str) → Any[source]
get_attr_node(node: Hashable, attr: str) → Any[source]
get_edges() → KeysView[Tuple[Hashable, Hashable]][source]
get_neighbors(node: Hashable) → Set[Hashable][source]
get_nodes() → List[Hashable][source]
get_predecessors(node: Hashable) → Set[Hashable][source]
precedessors_nodes(n: Hashable) → Set[Hashable][source]
predecessors_map() → Dict[Hashable, List[Hashable]][source]
successors_map() → Dict[Hashable, List[Hashable]][source]
to_networkx() → DiGraph[source]
discrete_optimization.generic_tools.graph_api.from_networkx(graph_nx: DiGraph | Graph, undirected: bool | None = None, compute_predecessors: bool = False)[source]
discrete_optimization.generic_tools.graph_api.get_node_attributes(graph: ~networkx.classes.graph.Graph, name: <module 'string' from '/opt/hostedtoolcache/Python/3.9.19/x64/lib/python3.9/string.py'>, default: ~typing.Any)[source]

@param graph: a nx.Graph @param name: name of attribut of intereste @param default: default value if no value for attribute of interest @return: a dictionnary with for each node of graph, the attribute value corresponding

discrete_optimization.generic_tools.lns_cp module

class discrete_optimization.generic_tools.lns_cp.ConstraintHandler[source]

Bases: Hyperparametrizable

abstract adding_constraint_from_results_store(cp_solver: CPSolver, child_instance: Instance, result_storage: ResultStorage, last_result_store: ResultStorage | None = None) → Iterable[Any][source]
abstract remove_constraints_from_previous_iteration(cp_solver: CPSolver, child_instance: Instance, previous_constraints: Iterable[Any]) → None[source]
class discrete_optimization.generic_tools.lns_cp.ConstraintHandlerMix(problem: Problem, list_constraints_handler: List[ConstraintHandler], list_proba: List[float], update_proba: bool = True, tag_constraint_handler: List[str] | None = None, sequential: bool = False)[source]

Bases: ConstraintHandler

adding_constraint_from_results_store(cp_solver: CPSolver, child_instance: Instance, result_storage: ResultStorage, last_result_store: ResultStorage | None = None) → Iterable[Any][source]
remove_constraints_from_previous_iteration(cp_solver: CPSolver, child_instance: Instance, previous_constraints: Iterable[Any]) → None[source]
class discrete_optimization.generic_tools.lns_cp.ConstraintStatus[source]

Bases: TypedDict

name: str
nb_improvement: int
nb_usage: int
class discrete_optimization.generic_tools.lns_cp.LNS_CP(problem: Problem, cp_solver: MinizincCPSolver | None = None, initial_solution_provider: InitialSolution | None = None, constraint_handler: ConstraintHandler | None = None, post_process_solution: PostProcessSolution | None = None, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverDO

hyperparameters: List[Hyperparameter] = [SubBrickHyperparameter(name='cp_solver_cls', default=None, choices=[]), SubBrickKwargsHyperparameter(name='cp_solver_kwargs', default=None), SubBrickHyperparameter(name='initial_solution_provider_cls', default=None, choices=[]), SubBrickKwargsHyperparameter(name='initial_solution_provider_kwargs', default=None), SubBrickHyperparameter(name='constraint_handler_cls', default=None, choices=[]), SubBrickKwargsHyperparameter(name='constraint_handler_kwargs', default=None), SubBrickHyperparameter(name='post_process_solution_cls', default=<class 'discrete_optimization.generic_tools.lns_mip.TrivialPostProcessSolution'>, choices=[]), SubBrickKwargsHyperparameter(name='post_process_solution_kwargs', default=None), CategoricalHyperparameter(name='skip_first_iteration', default=False, choices=[True, False])]

Hyperparameters available for this solver.

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

  • __init__()

  • init_model() (when available)

  • solve()

solve(nb_iteration_lns: int, parameters_cp: ParametersCP | None = None, nb_iteration_no_improvement: int | None = None, skip_first_iteration: bool = False, stop_first_iteration_if_optimal: bool = True, callbacks: List[Callback] | None = None, **kwargs: Any) → ResultStorage[source]

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_lns(parameters_cp: ParametersCP, nb_iteration_lns: int, nb_iteration_no_improvement: int | None = None, skip_first_iteration: bool = False, stop_first_iteration_if_optimal: bool = True, callbacks: List[Callback] | None = None, **kwargs: Any) → ResultStorage[source]
class discrete_optimization.generic_tools.lns_cp.LNS_CPlex(problem: Problem, cp_solver: CPSolver, initial_solution_provider: InitialSolution, constraint_handler: ConstraintHandler, post_process_solution: PostProcessSolution | None = None, params_objective_function: ParamsObjectiveFunction | None = None)[source]

Bases: SolverDO

solve(nb_iteration_lns: int, parameters_cp: ParametersCP | None = None, nb_iteration_no_improvement: int | None = None, skip_first_iteration: bool = False, callbacks: List[Callback] | None = None, **kwargs: Any) → ResultStorage[source]

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_lns(parameters_cp: ParametersCP, nb_iteration_lns: int, nb_iteration_no_improvement: int | None = None, skip_first_iteration: bool = False, callbacks: List[Callback] | None = None, **kwargs: Any) → ResultStorage[source]

discrete_optimization.generic_tools.lns_mip module

class discrete_optimization.generic_tools.lns_mip.ConstraintHandler[source]

Bases: Hyperparametrizable

abstract adding_constraint_from_results_store(milp_solver: MilpSolver, result_storage: ResultStorage) → Mapping[Hashable, Any][source]
abstract remove_constraints_from_previous_iteration(milp_solver: MilpSolver, previous_constraints: Mapping[Hashable, Any]) → None[source]
class discrete_optimization.generic_tools.lns_mip.InitialSolution[source]

Bases: Hyperparametrizable

abstract get_starting_solution() → ResultStorage[source]
class discrete_optimization.generic_tools.lns_mip.InitialSolutionFromSolver(solver: SolverDO, **kwargs: Any)[source]

Bases: InitialSolution

abstract get_starting_solution() → ResultStorage[source]
class discrete_optimization.generic_tools.lns_mip.LNS_MILP(problem: Problem, milp_solver: MilpSolver, initial_solution_provider: InitialSolution, constraint_handler: ConstraintHandler, post_process_solution: PostProcessSolution | None = None, params_objective_function: ParamsObjectiveFunction | None = None)[source]

Bases: SolverDO

solve(parameters_milp: ParametersMilp, nb_iteration_lns: int, nb_iteration_no_improvement: int | None = None, skip_first_iteration: bool | None = False, callbacks: List[Callback] | None = None, **kwargs: Any) → ResultStorage[source]

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_lns(parameters_milp: ParametersMilp, nb_iteration_lns: int, nb_iteration_no_improvement: int | None = None, skip_first_iteration: bool | None = False, callbacks: List[Callback] | None = None, **args: Any) → ResultStorage[source]
class discrete_optimization.generic_tools.lns_mip.PostProcessSolution[source]

Bases: Hyperparametrizable

abstract build_other_solution(result_storage: ResultStorage) → ResultStorage[source]
class discrete_optimization.generic_tools.lns_mip.TrivialInitialSolution(solution: ResultStorage, **kwargs: Any)[source]

Bases: InitialSolution

abstract get_starting_solution() → ResultStorage[source]
class discrete_optimization.generic_tools.lns_mip.TrivialPostProcessSolution(**kwargs)[source]

Bases: PostProcessSolution

build_other_solution(result_storage: ResultStorage) → ResultStorage[source]

discrete_optimization.generic_tools.lp_tools module

class discrete_optimization.generic_tools.lp_tools.CplexMilpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: MilpSolver

get_obj_value_for_ith_solution(i: int) → float[source]

Get objective value for i-th solution.

get_var_value_for_ith_solution(var: Var, i: int) → float[source]

Get value for i-th solution of a given variable.

model: docplex.mp.model.Model | None
property nb_solutions: int

Number of solutions found by the solver.

results_solve: List[SolveSolution] | None
solve(parameters_milp: ParametersMilp | None = None, **kwargs: Any) → ResultStorage[source]

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.generic_tools.lp_tools.GurobiCallback(do_solver: GurobiMilpSolver, callback: Callback)[source]

Bases: object

class discrete_optimization.generic_tools.lp_tools.GurobiMilpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: MilpSolver

Milp solver wrapping a solver from gurobi library.

early_stopping_exception: Exception | None = None
get_obj_value_for_ith_solution(i: int) → float[source]

Get objective value for i-th solution.

get_var_value_for_ith_solution(var: gurobipy.Var, i: int)[source]

Get value for i-th solution of a given variable.

model: gurobipy.Model | None = None
property nb_solutions: int

Number of solutions found by the solver.

optimize_model(parameters_milp: ParametersMilp | None = None, **kwargs: Any) → None[source]

Optimize the Gurobi Model.

The solutions are yet to be retrieved via self.retrieve_solutions(). No callbacks are passed to the internal solver, and no result_storage is created

prepare_model(parameters_milp: ParametersMilp | None = None, **kwargs: Any) → None[source]

Set Gurobi Model parameters according to parameters_milp

solve(callbacks: List[Callback] | None = None, parameters_milp: ParametersMilp | None = None, **kwargs: Any) → ResultStorage[source]

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.generic_tools.lp_tools.MilpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverDO

abstract get_obj_value_for_ith_solution(i: int) → float[source]

Get objective value for i-th solution.

abstract get_var_value_for_ith_solution(var: Any, i: int) → float[source]

Get value for i-th solution of a given variable.

abstract init_model(**kwargs: Any) → None[source]

Initialize intern model used to solve.

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

model: Any | None
abstract property nb_solutions: int

Number of solutions found by the solver.

abstract retrieve_current_solution(get_var_value_for_current_solution: Callable[[Any], float], get_obj_value_for_current_solution: Callable[[], float]) → Solution[source]

Retrieve current solution from internal gurobi solution.

This converts internal gurobi solution into a discrete-optimization Solution. This method can be called after the solve in retrieve_solutions() or during solve within a gurobi/pymilp/cplex callback. The difference will be the get_var_value_for_current_solution and get_obj_value_for_current_solution callables passed.

Parameters:

  • get_var_value_for_current_solution – function extracting the value of the given variable for the current solution will be different when inside a callback or after the solve is finished

  • get_obj_value_for_current_solution – function extracting the value of the objective for the current solution.

Returns:

the converted solution at d-o format

retrieve_ith_solution(i: int) → Solution[source]

Retrieve i-th solution from internal milp model.

Parameters:

i

Returns:

retrieve_solutions(parameters_milp: ParametersMilp, **kwargs) → ResultStorage[source]

Retrieve solutions found by internal solver.

Parameters:

  • parameters_milp

  • **kwargs – passed to ResultStorage.__init__()

Returns:

abstract solve(callbacks: List[Callback] | None = None, parameters_milp: ParametersMilp | None = None, **kwargs: Any) → ResultStorage[source]

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.generic_tools.lp_tools.MilpSolverName(value)[source]

Bases: Enum

An enumeration.

CBC = 0
GRB = 1
class discrete_optimization.generic_tools.lp_tools.ParametersMilp(time_limit: int, pool_solutions: int, mip_gap_abs: float, mip_gap: float, retrieve_all_solution: bool, n_solutions_max: int, pool_search_mode: int = 0)[source]

Bases: object

static default() → ParametersMilp[source]
class discrete_optimization.generic_tools.lp_tools.PymipMilpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: MilpSolver

Milp solver wrapping a solver from pymip library.

get_obj_value_for_ith_solution(i: int) → float[source]

Get objective value for i-th solution.

get_var_value_for_ith_solution(var: Var, i: int) → float[source]

Get value for i-th solution of a given variable.

model: Model | None = None
property nb_solutions: int

Number of solutions found by the solver.

optimize_model(parameters_milp: ParametersMilp | None = None, **kwargs: Any) → None[source]

Optimize the mip Model.

The solutions are yet to be retrieved via self.retrieve_solutions().

prepare_model(parameters_milp: ParametersMilp | None = None, **kwargs: Any) → None[source]

Set Gurobi Model parameters according to parameters_milp

solve(parameters_milp: ParametersMilp | None = None, **kwargs: Any) → ResultStorage[source]

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

discrete_optimization.generic_tools.ortools_cpsat_tools module

class discrete_optimization.generic_tools.ortools_cpsat_tools.OrtoolsCPSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: CPSolver

Generic ortools cp-sat solver.

cp_model: CpModel | None = None
early_stopping_exception: Exception | None = None
abstract retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → Solution[source]

Construct a do solution from the cpsat solver internal solution.

It will be called each time the cpsat solver find a new solution. At that point, value of internal variables are accessible via cpsolvercb.Value(VARIABLE_NAME).

Parameters:

cpsolvercb – the ortools callback called when the cpsat solver finds a new solution.

Returns:

the intermediate solution, at do format.

solve(callbacks: List[Callback] | None = None, parameters_cp: ParametersCP | None = None, **kwargs: Any) → ResultStorage[source]

Solve the problem with a CPSat solver drom ortools library.

Parameters:

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

  • parameters_cp – parameters specific to cp solvers. We use here only parameters_cp.time_limit and parameters_cp.nb_process.

  • **kwargs – keyword arguments passed to self.init_model()

Returns:

A dedicated ortools callback is used to: - update a resultstorage each time a new solution is found by the cpsat solver. - call the user (do) callbacks at each new solution, with the possibility of early stopping if the callback return True.

This ortools callback use the method self.retrieve_solution() to reconstruct a do Solution from the cpsat solve internal state.

class discrete_optimization.generic_tools.ortools_cpsat_tools.OrtoolsCallback(do_solver: OrtoolsCPSatSolver, callback: Callback)[source]

Bases: CpSolverSolutionCallback

on_solution_callback() → None[source]
store_current_solution()[source]
discrete_optimization.generic_tools.ortools_cpsat_tools.cpstatus_to_dostatus(status_from_cpsat) → StatusSolver[source]
Parameters:

status_from_cpsat – either [UNKNOWN,INFEASIBLE,OPTIMAL,FEASIBLE] from ortools.cp api.

Returns:

Status

discrete_optimization.generic_tools.path_tools module

discrete_optimization.generic_tools.path_tools.abspath_from_file(file: str, relative_path: str) → str[source]
discrete_optimization.generic_tools.path_tools.get_directory(file: str) → str[source]

discrete_optimization.generic_tools.plot_utils module

Contains common utilities to plot solution, for now it’s mainly to patch API break happening with matplotlib3.9.0 on colors.

discrete_optimization.generic_tools.plot_utils.get_cmap(color_map_str: str)[source]
discrete_optimization.generic_tools.plot_utils.get_cmap_with_nb_colors(color_map_str: str, nb_colors: int = 2)[source]

discrete_optimization.generic_tools.qiskit_tools module

class discrete_optimization.generic_tools.qiskit_tools.QiskitQAOASolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverDO

abstract init_model(**kwargs: Any) → None[source]

Initialize intern model used to solve.

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

abstract retrieve_current_solution(result) → Solution[source]

Retrieve current solution from qiskit result.

Parameters:

result – list of value for each binary variable of the problem

Returns:

the converted solution at d-o format

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

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.generic_tools.qiskit_tools.QiskitVQESolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverDO

abstract init_model(**kwargs: Any) → None[source]

Initialize intern model used to solve.

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

abstract retrieve_current_solution(result) → Solution[source]

Retrieve current solution from qiskit result.

Parameters:

result – list of value for each binary variable of the problem

Returns:

the converted solution at d-o format

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

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

Module contents