discrete_optimization.facility.solvers package

Submodules

discrete_optimization.facility.solvers.facility_cp_solvers module

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

Bases: MinizincCPSolver, SolverFacility

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=<FacilityCPModel.DEFAULT_INT: 0>, choices=[<FacilityCPModel.DEFAULT_INT: 0>, <FacilityCPModel.DEFAULT_INT_LNS: 1>]), 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()

init_model(**kwargs: Any) → None

Initialise the minizinc instance to solve for a given instance.

Keyword Arguments:

• cp_model (FacilityCPModel) – 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:

class discrete_optimization.facility.solvers.facility_cp_solvers.FacilityCPModel(value)

Bases: Enum

An enumeration.

DEFAULT_INT = 0

DEFAULT_INT_LNS = 1

discrete_optimization.facility.solvers.facility_lp_lns_solver module

class discrete_optimization.facility.solvers.facility_lp_lns_solver.ConstraintHandlerFacility(problem: FacilityProblem, fraction_to_fix: float = 0.9, skip_first_iter: bool = True)

Bases: ConstraintHandler

Constraint builder used in LNS+LP for coloring problem.

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(milp_solver: MilpSolver, result_storage: ResultStorage) → Mapping[Hashable, Any]

remove_constraints_from_previous_iteration(milp_solver: MilpSolver, previous_constraints: Mapping[Hashable, Any]) → None

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

Bases: Enum

An enumeration.

DUMMY = 0

GREEDY = 1

class discrete_optimization.facility.solvers.facility_lp_lns_solver.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, choices=[<InitialFacilityMethod.DUMMY: 0>, <InitialFacilityMethod.GREEDY: 1>])]

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.facility_lp_solver module

Linear programming models and solve functions for facility location problem.

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

Bases: GurobiMilpSolver, _LPFacilitySolverBase

Milp solver using gurobi library

coloring_model

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

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.facility_lp_solver.LP_Facility_Solver_CBC(problem: FacilityProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverFacility

Milp formulation using cbc solver.

hyperparameters: List[Hyperparameter] = [CategoricalHyperparameter(name='use_matrix_indicator_heuristic', default=True, choices=[False, True]), IntegerHyperparameter(name='n_shortest', default=10, low=0, high=100), IntegerHyperparameter(name='n_cheapest', default=10, low=0, high=100)]

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 intern model used to solve.

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

retrieve() → ResultStorage

solve(parameters_milp: ParametersMilp | 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.facility.solvers.facility_lp_solver.LP_Facility_Solver_PyMip(problem: FacilityProblem, milp_solver_name: MilpSolverName, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: PymipMilpSolver, _LPFacilitySolverBase

Milp solver using pymip library

Note

Gurobi and CBC are available backends.

init_model(**kwargs: Any) → None

Initialize intern model used to solve.

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

discrete_optimization.facility.solvers.facility_lp_solver.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.facility_lp_solver.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.facility_solver module

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

Bases: SolverDO

problem: FacilityProblem

discrete_optimization.facility.solvers.gphh_facility module

Genetic programming based solver for facility location problem.

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

Bases: Enum

An enumeration.

CAPACITIES = 'capacities'

DEMAND_MINUS_CAPACITY = 'demand_minus_capacity'

DISTANCE = 'distance'

class discrete_optimization.facility.solvers.gphh_facility.GPHH(training_domains: List[FacilityProblem], problem: FacilityProblem, weight: int = 1, params_gphh: ParametersGPHH | None = None, params_objective_function: ParamsObjectiveFunction | None = None)

Bases: SolverFacility

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 intern 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_facility.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 GPHH 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_facility.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_facility.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_facility.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_facility.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_solvers module

class discrete_optimization.facility.solvers.greedy_solvers.GreedySolverDistanceBased(problem: FacilityProblem, params_objective_function: ParamsObjectiveFunction | None = None)

Bases: SolverFacility

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_solvers.GreedySolverFacility(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverFacility

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

Module contents