discrete_optimization.facility.solvers package

Submodules

discrete_optimization.facility.solvers.cp_mzn module

class discrete_optimization.facility.solvers.cp_mzn.CpFacilityModel(value)

Bases: Enum

An enumeration.

DEFAULT_INT = 0

DEFAULT_INT_LNS = 1

class discrete_optimization.facility.solvers.cp_mzn.CpFacilitySolver(problem: FacilityProblem, params_objective_function: ParamsObjectiveFunction | None = None, silent_solve_error: bool = False, **kwargs: Any)

Bases: MinizincCpSolver, FacilitySolver

CP solver linked with minizinc implementation of coloring problem.

problem

facility problem instance to solve

Type:

FacilityProblem

params_objective_function

params of the objective function

Type:

ParamsObjectiveFunction

cp_solver_name

backend solver to use with minizinc

Type:

CpSolverName

silent_solve_error

if True, raise a warning instead of an error if the underlying instance.solve() crashes

Type:

bool

\*\*args

unused

hyperparameters: list[Hyperparameter] = [EnumHyperparameter(name='cp_model', default=<CpFacilityModel.DEFAULT_INT: 0>, depends_on=None, name_in_kwargs='cp_model'), EnumHyperparameter(name='cp_solver_name', default=<CpSolverName.CHUFFED: 0>, depends_on=None, name_in_kwargs='cp_solver_name')]

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

Initialise the minizinc instance to solve for a given instance.

Keyword Arguments:

• cp_model (CpFacilityModel) – CP model version

• object_output (bool) – specify if the solution are returned in a FacilitySolCp object or native minizinc output.

Returns: None

retrieve_solution(_output_item: str | None = None, **kwargs: Any) → FacilitySolution

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:

discrete_optimization.facility.solvers.dp module

class discrete_optimization.facility.solvers.dp.DpFacilityModeling(value)

Bases: Enum

An enumeration.

CUSTOMER = 0

FACILITY = 1

class discrete_optimization.facility.solvers.dp.DpFacilitySolver(problem: FacilityProblem, **kwargs: Any)

Bases: DpSolver, FacilitySolver, WarmstartMixin

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='solver', default=<class 'builtins.CABS'>, depends_on=None, name_in_kwargs='solver'), EnumHyperparameter(name='modeling', default=<DpFacilityModeling.CUSTOMER: 0>, depends_on=None, name_in_kwargs='modeling')]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

init_model(modeling: DpFacilityModeling = DpFacilityModeling.CUSTOMER, **kwargs: Any) → None

Initialize internal model used to solve.

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

init_model_customer_view(**kwargs: Any) → None

init_model_factory_view(**kwargs: Any) → None

retrieve_solution(sol: Solution) → Solution

retrieve_solution_customer_view(sol: Solution) → Solution

retrieve_solution_factory_view(sol: Solution) → Solution

set_warm_start(solution: FacilitySolution) → None

Make the solver warm start from the given solution.

discrete_optimization.facility.solvers.facility_solver module

class discrete_optimization.facility.solvers.facility_solver.FacilitySolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

problem: FacilityProblem

discrete_optimization.facility.solvers.gphh module

Genetic programming based solver for facility location problem.

class discrete_optimization.facility.solvers.gphh.FeatureEnum(value)

Bases: Enum

An enumeration.

CAPACITIES = 'capacities'

DEMAND_MINUS_CAPACITY = 'demand_minus_capacity'

DISTANCE = 'distance'

class discrete_optimization.facility.solvers.gphh.GphhFacilitySolver(problem: FacilityProblem, training_domains: list[FacilityProblem] | None = None, weight: int = 1, params_gphh: ParametersGphh | None = None, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: FacilitySolver

build_solution(domain: FacilityProblem, individual: Any | None = None, func_heuristic: Callable[[...], _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes]] | None = None) → ResultStorage

evaluate_complexity(individual: Any) → float

evaluate_heuristic(individual: Any, domains: list[FacilityProblem]) → list[float]

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

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

init_primitives(pset: PrimitiveSetTyped) → PrimitiveSet

plot_solution() → None

solve(**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.facility.solvers.gphh.ParametersGphh(set_feature: set[FeatureEnum], set_primitives: PrimitiveSetTyped, tournament_ratio: float, pop_size: int, n_gen: int, min_tree_depth: int, max_tree_depth: int, crossover_rate: float, mutation_rate: float, deap_verbose: bool)

Bases: object

Custom class to parametrize the GphhGenericRcpspSolver solver.

set_feature

the set of feature to consider

set_primitives

set of operator/primitive to consider.

static default() → ParametersGphh

discrete_optimization.facility.solvers.gphh.capacity(problem: FacilityProblem, customer_index: int, **kwargs: Any) → list[float]

Capacity feature. :param problem: problem instance :type problem: FacilityProblem :param customer_index: [unused] customer index to compute distances to facilities :type customer_index: int

discrete_optimization.facility.solvers.gphh.closest_facility(problem: FacilityProblem, customer_index: int, **kwargs: Any) → int

Closest facility feature for a given customer index.

Parameters:

• problem (FacilityProblem) – problem instance

• customer_index (int) – [unused] customer index to compute distances to facilities

Returns (int): closest facility index

discrete_optimization.facility.solvers.gphh.demand_minus_capacity(problem: FacilityProblem, customer_index: int, **kwargs: Any) → list[float]

Compute demand-capacity feature for a given customer_index

Parameters:

• problem (FacilityProblem) – problem instance

• customer_index (int) – customer index to compute distances to facilities

discrete_optimization.facility.solvers.gphh.distance(problem: FacilityProblem, customer_index: int, **kwargs: Any) → list[float]

Compute distance to facilitied for a given customer index

Parameters:

• problem (FacilityProblem) – problem instance

• customer_index (int) – customer index to compute distances to facilities

discrete_optimization.facility.solvers.greedy module

class discrete_optimization.facility.solvers.greedy.DistanceBasedGreedyFacilitySolver(problem: FacilityProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: FacilitySolver

solve(**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.facility.solvers.greedy.GreedyFacilitySolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: FacilitySolver

build a trivial solution pack the facilities one by one until all the customers are served

solve(**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

discrete_optimization.facility.solvers.lns_lp module

class discrete_optimization.facility.solvers.lns_lp.GurobiFacilityConstraintHandler(problem: FacilityProblem, fraction_to_fix: float = 0.9)

Bases: GurobiConstraintHandler, _BaseFacilityConstraintHandler

Constraint builder used in LNS+LP for coloring problem with gurobi solver.

This constraint handler is pretty basic, it fixes a fraction_to_fix proportion of allocation of customer to facility.

problem

input coloring problem

Type:

ColoringProblem

fraction_to_fix

float between 0 and 1, representing the proportion of nodes to constrain.

Type:

float

adding_constraint_from_results_store(solver: GurobiFacilitySolver, result_storage: ResultStorage, **kwargs: Any) → Iterable[Any]

class discrete_optimization.facility.solvers.lns_lp.InitialFacilityMethod(value)

Bases: Enum

An enumeration.

DUMMY = 0

GREEDY = 1

class discrete_optimization.facility.solvers.lns_lp.InitialFacilitySolution(problem: FacilityProblem, initial_method: InitialFacilityMethod, params_objective_function: ParamsObjectiveFunction)

Bases: InitialSolution

Initial solution provider for lns algorithm.

problem

input coloring problem

Type:

FacilityProblem

initial_method

the method to use to provide the initial solution.

Type:

InitialFacilityMethod

get_starting_solution() → ResultStorage

hyperparameters: list[Hyperparameter] = [EnumHyperparameter(name='initial_method', default=None, depends_on=None, name_in_kwargs='initial_method')]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

class discrete_optimization.facility.solvers.lns_lp.MathOptConstraintHandlerFacility(problem: FacilityProblem, fraction_to_fix: float = 0.9)

Bases: OrtoolsMathOptConstraintHandler, _BaseFacilityConstraintHandler

Constraint builder used in LNS+LP for coloring problem with mathopt solver.

This constraint handler is pretty basic, it fixes a fraction_to_fix proportion of allocation of customer to facility.

problem

input coloring problem

Type:

ColoringProblem

fraction_to_fix

float between 0 and 1, representing the proportion of nodes to constrain.

Type:

float

adding_constraint_from_results_store(solver: MathOptFacilitySolver, result_storage: ResultStorage, **kwargs: Any) → Iterable[Any]

discrete_optimization.facility.solvers.lp module

Linear programming models and solve functions for facility location problem.

class discrete_optimization.facility.solvers.lp.CbcFacilitySolver(problem: FacilityProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: FacilitySolver

Milp formulation using cbc solver.

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='use_matrix_indicator_heuristic', default=True, depends_on=None, name_in_kwargs='use_matrix_indicator_heuristic'), IntegerHyperparameter(name='n_shortest', default=10, depends_on=None, name_in_kwargs='n_shortest', low=0, high=100, step=1, log=False), IntegerHyperparameter(name='n_cheapest', default=10, depends_on=None, name_in_kwargs='n_cheapest', low=0, high=100, step=1, log=False)]

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.

model: pywraplp.Solver | None

retrieve() → ResultStorage

solve(parameters_milp: ParametersMilp | None = None, time_limit: int | None = 30, **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.facility.solvers.lp.GurobiFacilitySolver(problem: FacilityProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: GurobiMilpSolver, _BaseLpFacilitySolver

Milp solver using gurobi library

coloring_problem

facility problem instance to solve

Type:

FacilityProblem

params_objective_function

objective function parameters (however this is just used for the ResultStorage creation, not in the optimisation)

Type:

ParamsObjectiveFunction

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().

init_model(**kwargs: Any) → None

Keyword Arguments:

• use_matrix_indicator_heuristic (bool) – use the prune search method to reduce number of variable.

• n_shortest (int) – parameter for the prune search method

• n_cheapest (int) – parameter for the prune search method

Returns: None

class discrete_optimization.facility.solvers.lp.MathOptFacilitySolver(problem: FacilityProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OrtoolsMathOptMilpSolver, _BaseLpFacilitySolver

Milp solver using gurobi library

coloring_problem

facility problem instance to solve

Type:

FacilityProblem

params_objective_function

objective function parameters (however this is just used for the ResultStorage creation, not in the optimisation)

Type:

ParamsObjectiveFunction

convert_to_variable_values(solution: FacilitySolution) → 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.

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='use_matrix_indicator_heuristic', default=True, depends_on=None, name_in_kwargs='use_matrix_indicator_heuristic'), IntegerHyperparameter(name='n_shortest', default=10, depends_on=('use_matrix_indicator_heuristic', [True]), name_in_kwargs='n_shortest', low=0, high=100, step=1, log=False), IntegerHyperparameter(name='n_cheapest', default=10, depends_on=('use_matrix_indicator_heuristic', [True]), name_in_kwargs='n_cheapest', low=0, high=100, step=1, log=False)]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

discrete_optimization.facility.solvers.lp.compute_length_matrix(facility_problem: FacilityProblem) → tuple[ndarray[Any, dtype[float64]], ndarray[Any, dtype[int64]], ndarray[Any, dtype[float64]]]

Precompute all the cost of allocation in a matrix form.

A matrix “closest” is also computed, sorting for each customers the facility by distance.

Parameters:

facility_problem (FacilityProblem) – facility problem instance to compute cost matrix

Returns: setup cost vector, sorted matrix distance, matrix distance

discrete_optimization.facility.solvers.lp.prune_search_space(facility_problem: FacilityProblem, n_cheapest: int = 10, n_shortest: int = 10) → tuple[ndarray, ndarray]

Utility function that can prune the search space.

Output of this function will be used to : - consider only the n_cheapest facility that has the cheapest setup_cost - consider only the n_shortest (closest actually) facilities for each customers

Parameters:

• facility_problem (FacilityProblem) – facility problem instance

• n_cheapest (int) – select the cheapest setup cost facilities

• n_shortest (int) – for each customer, select the closest facilities

Returns: tuple of matrix, first element is a matrix (facility_count, customer_count) with 2 as value when we should consider the allocation possible. Second element in the (facility,customer) matrix distance.

discrete_optimization.facility.solvers.quantum module

class discrete_optimization.facility.solvers.quantum.FacilityQiskit(problem: FacilityProblem)

Bases: object

interpret(result: object | ndarray)

to_quadratic_program() → object

class discrete_optimization.facility.solvers.quantum.QaoaFacilitySolver(problem: FacilityProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: FacilitySolver, QiskitQaoaSolver

init_model(**kwargs)

Initialize internal model used to solve.

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

retrieve_current_solution(result) → Solution

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

class discrete_optimization.facility.solvers.quantum.VqeFacilitySolver(problem: FacilityProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: FacilitySolver, QiskitVqeSolver

init_model(**kwargs)

Initialize internal model used to solve.

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

retrieve_current_solution(result) → Solution

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

Module contents