discrete_optimization.knapsack.solvers package

Submodules

discrete_optimization.knapsack.solvers.cp_solvers module

class discrete_optimization.knapsack.solvers.cp_solvers.CPKnapsackMZN(problem: KnapsackModel, params_objective_function: ParamsObjectiveFunction | None = None, silent_solve_error: bool = False, **kwargs: Any)

Bases: MinizincCPSolver, SolverKnapsack

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

init_model(**kwargs: Any) → None

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

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

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.knapsack.solvers.cp_solvers.CPKnapsackMZN2(problem: KnapsackModel, params_objective_function: ParamsObjectiveFunction | None = None, silent_solve_error: bool = False, **kwargs: Any)

Bases: MinizincCPSolver, SolverKnapsack

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

init_model(**kwargs: Any) → None

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

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

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.knapsack.solvers.cp_solvers.CPMultidimensionalMultiScenarioSolver(problem: MultiScenarioMultidimensionalKnapsack, params_objective_function: ParamsObjectiveFunction | None = None, silent_solve_error: bool = False, **kwargs: Any)

Bases: MinizincCPSolver

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

init_model(**kwargs: Any) → None

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

problem: MultiScenarioMultidimensionalKnapsack

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

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.knapsack.solvers.cp_solvers.CPMultidimensionalSolver(problem: MultidimensionalKnapsack, params_objective_function: ParamsObjectiveFunction | None = None, silent_solve_error: bool = False, **kwargs: Any)

Bases: MinizincCPSolver

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

init_model(**kwargs: Any) → None

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

problem: MultidimensionalKnapsack

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

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.knapsack.solvers.cp_solvers.KnapConstraintHandler(fraction_fix: float = 0.95)

Bases: ConstraintHandler

adding_constraint_from_results_store(cp_solver: CPSolver, child_instance: Instance, result_storage: ResultStorage, last_result_store: ResultStorage | None = None) → Iterable[Any]

hyperparameters: List[Hyperparameter] = [FloatHyperparameter(name='fraction_fix', default=0.95, low=0.0, high=1.0)]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

remove_constraints_from_previous_iteration(cp_solver: CPSolver, child_instance: Instance, previous_constraints: Iterable[Any]) → None

discrete_optimization.knapsack.solvers.dyn_prog_knapsack module

class discrete_optimization.knapsack.solvers.dyn_prog_knapsack.KnapsackDynProg(problem: KnapsackModel, params_objective_function: ParamsObjectiveFunction | None = None)

Bases: SolverKnapsack

hyperparameters: List[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', 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(**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.knapsack.solvers.gphh_knapsack module

class discrete_optimization.knapsack.solvers.gphh_knapsack.FeatureEnum(value)

Bases: Enum

An enumeration.

AVG_RES_CONSUMPTION_DELTA_CAPACITY = 'avg_res_consumption_delta_capacity'

CAPACITIES = 'capacities'

PROFIT = 'profit'

RES_CONSUMPTION_ARRAY = 'res_consumption'

class discrete_optimization.knapsack.solvers.gphh_knapsack.GPHH(training_domains: List[Problem], problem: MultidimensionalKnapsack, weight: int = 1, params_gphh: ParametersGPHH | None = None, params_objective_function: ParamsObjectiveFunction | None = None)

Bases: SolverDO

build_result_storage_for_domain(domain: MultidimensionalKnapsack) → ResultStorage

build_solution(domain: MultidimensionalKnapsack, individual: Any | None = None, func_heuristic: Callable[[...], float] | None = None) → KnapsackSolutionMultidimensional

evaluate_complexity(individual: Any) → float

evaluate_heuristic(individual: Any, domains: List[MultidimensionalKnapsack]) → List[float]

hyperparameters: List[Hyperparameter] = [FloatHyperparameter(name='tournament_ratio', default=0.1, low=0, high=1.0), IntegerHyperparameter(name='pop_size', default=10, low=1, high=100), IntegerHyperparameter(name='min_tree_depth', default=1, low=1, high=20), IntegerHyperparameter(name='max_tree_depth', default=4, low=1, high=20), FloatHyperparameter(name='crossover_rate', default=0.7, low=0.0, high=1.0), FloatHyperparameter(name='mutation_rate', default=0.3, low=0, high=1.0), IntegerHyperparameter(name='n_gen', default=2, low=1, 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) → None

Initialize intern model used to solve.

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

init_primitives(pset: PrimitiveSetTyped) → PrimitiveSetTyped

plot_solution(show: bool = True) → 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

toolbox: Toolbox

class discrete_optimization.knapsack.solvers.gphh_knapsack.ParametersGPHH(list_feature: List[FeatureEnum], set_primitves: 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

static default() → ParametersGPHH

discrete_optimization.knapsack.solvers.gphh_knapsack.get_avg_res_consumption_delta_capacity(problem: MultidimensionalKnapsack, item_index: int, **kwargs: Any) → float

discrete_optimization.knapsack.solvers.gphh_knapsack.get_capacities(problem: MultidimensionalKnapsack, **kwargs: Any) → List[float]

discrete_optimization.knapsack.solvers.gphh_knapsack.get_profit(problem: MultidimensionalKnapsack, item_index: int, **kwargs: Any) → float

discrete_optimization.knapsack.solvers.gphh_knapsack.get_res_consumption(problem: MultidimensionalKnapsack, item_index: int, **kwargs: Any) → List[float]

discrete_optimization.knapsack.solvers.greedy_solvers module

class discrete_optimization.knapsack.solvers.greedy_solvers.GreedyBest(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverKnapsack

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.knapsack.solvers.greedy_solvers.GreedyDummy(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverKnapsack

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.knapsack.solvers.greedy_solvers.best_of_greedy(knapsack_model: KnapsackModel) → KnapsackSolution

discrete_optimization.knapsack.solvers.greedy_solvers.compute_density(knapsack_model: KnapsackModel) → List[Item]

discrete_optimization.knapsack.solvers.greedy_solvers.compute_density_and_penalty(knapsack_model: KnapsackModel) → List[Item]

discrete_optimization.knapsack.solvers.greedy_solvers.greedy_using_queue(knapsack_model: KnapsackModel, method_queue: Callable[[KnapsackModel], List[Item]] | None = None) → KnapsackSolution

discrete_optimization.knapsack.solvers.knapsack_asp_solver module

class discrete_optimization.knapsack.solvers.knapsack_asp_solver.KnapsackASPSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: ASPClingoSolver, SolverKnapsack

Solver based on Answer Set Programming formulation and clingo solver.

build_string_data_input()

init_model(**kwargs: Any) → None

Initialize intern model used to solve.

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

retrieve_solution(model: Model) → KnapsackSolution

Construct a do solution from a clingo model.

Parameters:

model – the current constructed clingo model

Returns:

the intermediate solution, at do format.

discrete_optimization.knapsack.solvers.knapsack_cpmpy module

class discrete_optimization.knapsack.solvers.knapsack_cpmpy.CPMPYKnapsackSolver(problem: KnapsackModel, params_objective_function: ParamsObjectiveFunction | None = None)

Bases: SolverKnapsack

init_model(**kwargs: Any) → None

Initialize intern model used to solve.

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

solve(parameters_cp: ParametersCP | 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

discrete_optimization.knapsack.solvers.knapsack_cpsat_solver module

class discrete_optimization.knapsack.solvers.knapsack_cpsat_solver.CPSatKnapsackSolver(problem: KnapsackModel, params_objective_function: ParamsObjectiveFunction | None = None)

Bases: OrtoolsCPSatSolver, SolverKnapsack

init_model(**args: Any) → None

Init CP model.

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → KnapsackSolution

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.

discrete_optimization.knapsack.solvers.knapsack_decomposition module

class discrete_optimization.knapsack.solvers.knapsack_decomposition.KnapsackDecomposedSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverKnapsack

This solver is based on the current observation. From a given knapsack model and one current solution, if we decide to freeze the decision variable for a subset of items, the remaining problem to solve is also a knapsack problem, with fewer items and smaller capacity. A solution to this subproblem can be found by any knapsack solver and a full solution to the original problem, can be rebuilt. KnapsackDecomposedSolver is a basic iterative solver that starts from a given solution, then freeze random items, solve subproblem with a custom root solver, rebuild original solution and repeat the process.

hyperparameters: List[Hyperparameter] = [FloatHyperparameter(name='proportion_to_remove', default=0.7, low=0.0, high=1.0), IntegerHyperparameter(name='nb_iteration', default=100, low=0, high=10000000), SubBrickHyperparameter(name='initial_solver', default=<class 'discrete_optimization.knapsack.solvers.greedy_solvers.GreedyBest'>, choices=[<class 'discrete_optimization.knapsack.solvers.lp_solvers.KnapsackORTools'>, <class 'discrete_optimization.knapsack.solvers.lp_solvers.LPKnapsack'>, <class 'discrete_optimization.knapsack.solvers.lp_solvers.LPKnapsackCBC'>, <class 'discrete_optimization.knapsack.solvers.lp_solvers.LPKnapsackGurobi'>, <class 'discrete_optimization.knapsack.solvers.knapsack_asp_solver.KnapsackASPSolver'>, <class 'discrete_optimization.knapsack.solvers.dyn_prog_knapsack.KnapsackDynProg'>, <class 'discrete_optimization.knapsack.solvers.cp_solvers.CPKnapsackMZN'>, <class 'discrete_optimization.knapsack.solvers.cp_solvers.CPKnapsackMZN2'>]), SubBrickKwargsHyperparameter(name='initial_solver_kwargs', default=None), SubBrickHyperparameter(name='root_solver', default=<class 'discrete_optimization.knapsack.solvers.greedy_solvers.GreedyBest'>, choices=[<class 'discrete_optimization.knapsack.solvers.lp_solvers.KnapsackORTools'>, <class 'discrete_optimization.knapsack.solvers.lp_solvers.LPKnapsack'>, <class 'discrete_optimization.knapsack.solvers.lp_solvers.LPKnapsackCBC'>, <class 'discrete_optimization.knapsack.solvers.lp_solvers.LPKnapsackGurobi'>, <class 'discrete_optimization.knapsack.solvers.knapsack_asp_solver.KnapsackASPSolver'>, <class 'discrete_optimization.knapsack.solvers.dyn_prog_knapsack.KnapsackDynProg'>, <class 'discrete_optimization.knapsack.solvers.cp_solvers.CPKnapsackMZN'>, <class 'discrete_optimization.knapsack.solvers.cp_solvers.CPKnapsackMZN2'>]), SubBrickKwargsHyperparameter(name='root_solver_kwargs', default=None)]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

rebuild_sol(sol: KnapsackSolution, original_knapsack_model: KnapsackModel, original_solution: KnapsackSolution, indexes_to_remove: Set[int])

Rebuild a knapsack solution object from a partial solution. :param sol: solution to a sub-knapsack problem :param original_knapsack_model: original knapsack model to solve :param original_solution: original base solution :param indexes_to_remove: indexes of item removed when building the sub-knapsack problem. :return: A new solution object for the original problem.

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

Generic solving function.

Parameters:

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

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

discrete_optimization.knapsack.solvers.knapsack_lns_cp_solver module

class discrete_optimization.knapsack.solvers.knapsack_lns_cp_solver.ConstraintHandlerKnapsack(problem: KnapsackModel, fraction_to_fix: float = 0.9)

Bases: ConstraintHandler

adding_constraint_from_results_store(cp_solver: CPSolver, child_instance: Instance, result_storage: ResultStorage, last_result_store: ResultStorage | None = None) → Iterable[Any]

hyperparameters: List[Hyperparameter] = [FloatHyperparameter(name='fraction_to_fix', default=0.9, low=0.0, high=1.0)]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

remove_constraints_from_previous_iteration(cp_solver: CPSolver, child_instance: Instance, previous_constraints: Iterable[Any]) → None

discrete_optimization.knapsack.solvers.knapsack_lns_solver module

class discrete_optimization.knapsack.solvers.knapsack_lns_solver.ConstraintHandlerKnapsack(problem: KnapsackModel, fraction_to_fix: float = 0.9)

Bases: ConstraintHandler

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.knapsack.solvers.knapsack_lns_solver.InitialKnapsackMethod(value)

Bases: Enum

An enumeration.

DUMMY = 0

GREEDY = 1

class discrete_optimization.knapsack.solvers.knapsack_lns_solver.InitialKnapsackSolution(problem: KnapsackModel, initial_method: InitialKnapsackMethod, params_objective_function: ParamsObjectiveFunction)

Bases: InitialSolution

get_starting_solution() → ResultStorage

hyperparameters: List[Hyperparameter] = [EnumHyperparameter(name='initial_method', default=None, choices=[<InitialKnapsackMethod.DUMMY: 0>, <InitialKnapsackMethod.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.knapsack.solvers.knapsack_solver module

class discrete_optimization.knapsack.solvers.knapsack_solver.SolverKnapsack(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

problem: KnapsackModel

discrete_optimization.knapsack.solvers.lp_solvers module

class discrete_optimization.knapsack.solvers.lp_solvers.KnapsackORTools(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverKnapsack

init_model(**kwargs: Any) → None

Initialize intern model used to solve.

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

model: KnapsackSolver | None = 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.knapsack.solvers.lp_solvers.LPKnapsack(problem: KnapsackModel, milp_solver_name: MilpSolverName = MilpSolverName.CBC, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: PymipMilpSolver, _BaseLPKnapsack

init_model(**kwargs: Any) → None

Initialize intern model used to solve.

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

class discrete_optimization.knapsack.solvers.lp_solvers.LPKnapsackCBC(problem: KnapsackModel, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverKnapsack

init_model(warm_start: Dict[int, int] | None = None, **kwargs: Any) → None

Initialize intern model used to solve.

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

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.knapsack.solvers.lp_solvers.LPKnapsackGurobi(problem: KnapsackModel, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: GurobiMilpSolver, _BaseLPKnapsack

init_model(**kwargs: Any) → None

Initialize intern model used to solve.

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

Module contents