discrete_optimization.knapsack package

Subpackages

Submodules

discrete_optimization.knapsack.mutation module

class discrete_optimization.knapsack.mutation.BitFlipMoveKP(attribute: str, problem: KnapsackProblem, list_index_flip: list[int])[source]

Bases: LocalMove

apply_local_move(solution: KnapsackSolution) → KnapsackSolution[source]
backtrack_local_move(solution: KnapsackSolution) → KnapsackSolution[source]
class discrete_optimization.knapsack.mutation.KnapsackMutationSingleBitFlip(problem: KnapsackProblem)[source]

Bases: Mutation

static build(knapsack_problem: KnapsackProblem, solution: Solution) → KnapsackMutatio.nSingleBitFlip[source]
mutate(solution: KnapsackSolution) → tuple[KnapsackSolution, LocalMove][source]
mutate_and_compute_obj(solution: KnapsackSolution) → tuple[KnapsackSolution, LocalMove, dict[str, float]][source]
class discrete_optimization.knapsack.mutation.MutationKnapsack(knapsack_problem: KnapsackProblem, attribute: str | None = None)[source]

Bases: Mutation

static build(knapsack_problem: KnapsackProblem, solution: Solution) → MutationKnapsack[source]
mutate(variable: KnapsackSolution) → tuple[KnapsackSolution, LocalMove][source]
mutate_and_compute_obj(variable: KnapsackSolution) → tuple[KnapsackSolution, LocalMove, dict[str, float]][source]
switch_off(variable: KnapsackSolution, come_from_outside: bool = False) → tuple[KnapsackSolution, LocalMove, dict[str, float]][source]
switch_on(variable: KnapsackSolution, come_from_outside: bool = False) → tuple[KnapsackSolution, LocalMove, dict[str, float]][source]
class discrete_optimization.knapsack.mutation.SingleBitFlipMove(i: int, problem: KnapsackProblem)[source]

Bases: LocalMove

apply_local_move(solution: KnapsackSolution) → KnapsackSolution[source]
backtrack_local_move(solution: KnapsackSolution) → KnapsackSolution[source]

discrete_optimization.knapsack.parser module

discrete_optimization.knapsack.parser.get_data_available(data_folder: str | None = None, data_home: str | None = None) → list[str][source]

Get datasets available for knapsack.

Params:
data_folder: folder where datasets for knapsack whould be find.

If None, we look in “knapsack” subdirectory of data_home.

data_home: root directory for all datasets. Is None, set by

default to “~/discrete_optimization_data “

discrete_optimization.knapsack.parser.parse_file(file_path: str, force_recompute_values: bool = False) → KnapsackProblem[source]
discrete_optimization.knapsack.parser.parse_input_data(input_data: str, force_recompute_values: bool = False) → KnapsackProblem[source]

Parse a string of the following form : item_count max_capacity item1_value item1_weight … itemN_value itemN_weight

discrete_optimization.knapsack.problem module

class discrete_optimization.knapsack.problem.Item(index: int, value: float, weight: float)[source]

Bases: object

index: int
value: float
weight: float
class discrete_optimization.knapsack.problem.ItemMultidimensional(index: int, value: float, weights: list[float])[source]

Bases: object

index: int
value: float
weights: list[float]
class discrete_optimization.knapsack.problem.KnapsackProblem(list_items: list[Item], max_capacity: float, force_recompute_values: bool = False)[source]

Bases: Problem

evaluate(knapsack_solution: KnapsackSolution) → 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_from_encoding(int_vector: list[int], encoding_name: str) → dict[str, float][source]
evaluate_value(knapsack_solution: KnapsackSolution) → float[source]
evaluate_weight_violation(knapsack_solution: KnapsackSolution) → float[source]
get_attribute_register() → EncodingRegister[source]

Returns how the Solution should be encoded.

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

get_dummy_solution() → KnapsackSolution[source]
get_objective_register() → ObjectiveRegister[source]

Returns the objective definition.

Returns (ObjectiveRegister): object defining the objective criteria.

get_solution_type() → type[Solution][source]

Returns the class implementation of a Solution.

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

satisfy(knapsack_solution: KnapsackSolution) → 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.knapsack.problem.KnapsackSolution(problem: KnapsackProblem, list_taken: list[int], value: float | None = None, weight: float | None = None)[source]

Bases: Solution

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

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

lazy_copy() → KnapsackSolution[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.knapsack.problem.MobjKnapsackModel(list_items: list[Item], max_capacity: float, force_recompute_values: bool = False)[source]

Bases: KnapsackProblem

evaluate(knapsack_solution: KnapsackSolution) → 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(solution: KnapsackSolution) → 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.

static from_knapsack(knapsack_problem: KnapsackProblem) → MobjKnapsackModel[source]
get_objective_register() → ObjectiveRegister[source]

Returns the objective definition.

Returns (ObjectiveRegister): object defining the objective criteria.

class discrete_optimization.knapsack.problem.MultiScenarioMultidimensionalKnapsackProblem(list_problem: Sequence[MultidimensionalKnapsackProblem], method_aggregating: MethodAggregating)[source]

Bases: RobustProblem

get_dummy_solution() → MultidimensionalKnapsackSolution[source]
list_problem: Sequence[MultidimensionalKnapsackProblem]
class discrete_optimization.knapsack.problem.MultidimensionalKnapsackProblem(list_items: list[ItemMultidimensional], max_capacities: list[float], force_recompute_values: bool = False)[source]

Bases: Problem

copy() → MultidimensionalKnapsackProblem[source]
evaluate(knapsack_solution: MultidimensionalKnapsackSolution) → 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_from_encoding(int_vector: list[int], encoding_name: str) → dict[str, float][source]
evaluate_value(knapsack_solution: MultidimensionalKnapsackSolution) → float[source]
evaluate_weight_violation(knapsack_solution: MultidimensionalKnapsackSolution) → float[source]
get_attribute_register() → EncodingRegister[source]

Returns how the Solution should be encoded.

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

get_dummy_solution() → MultidimensionalKnapsackSolution[source]
get_objective_register() → ObjectiveRegister[source]

Returns the objective definition.

Returns (ObjectiveRegister): object defining the objective criteria.

get_solution_type() → type[Solution][source]

Returns the class implementation of a Solution.

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

satisfy(knapsack_solution: MultidimensionalKnapsackSolution) → 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.knapsack.problem.MultidimensionalKnapsackSolution(problem: MultidimensionalKnapsackProblem | MultiScenarioMultidimensionalKnapsackProblem, list_taken: list[int], value: float | None = None, weights: list[float] | None = None)[source]

Bases: Solution

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

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

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

discrete_optimization.knapsack.problem.create_noised_scenario(problem: MultidimensionalKnapsackProblem, nb_scenarios: int = 20) → list[MultidimensionalKnapsackProblem][source]
discrete_optimization.knapsack.problem.create_subknapsack_problem(knapsack_problem: KnapsackProblem, solution: KnapsackSolution, indexes_to_remove: set[int], indexes_to_keep: set[int] | None = None)[source]
discrete_optimization.knapsack.problem.from_kp_to_multi(knapsack_problem: KnapsackProblem) → MultidimensionalKnapsackProblem[source]

discrete_optimization.knapsack.solvers_map module

discrete_optimization.knapsack.solvers_map.look_for_solver(domain: KnapsackProblem) → list[type[KnapsackSolver]][source]
discrete_optimization.knapsack.solvers_map.look_for_solver_class(class_domain: type[KnapsackProblem]) → list[type[KnapsackSolver]][source]
discrete_optimization.knapsack.solvers_map.solve(method: type[KnapsackSolver], problem: KnapsackProblem, **args: Any) → ResultStorage[source]

Module contents