discrete_optimization.knapsack package

Subpackages

Submodules

discrete_optimization.knapsack.mutation module

class discrete_optimization.knapsack.mutation.BitFlipKnapsackMutation(problem: KnapsackProblem, attribute: str | None = 'list_taken', **kwargs: Any)[source]

Bases: SingleAttributeMutation

attribute_type: ListBooleanKnapsack
attribute_type_cls

alias of ListBooleanKnapsack

mutate(solution: KnapsackSolution) → tuple[KnapsackSolution, LocalMove][source]
mutate_and_compute_obj(solution: KnapsackSolution) → tuple[KnapsackSolution, LocalMove, dict[str, float]][source]
problem: KnapsackProblem
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.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.SingleBitFlipKnapsackMutation(problem, attribute: str | None = 'list_taken', **kwargs: Any)[source]

Bases: SingleAttributeMutation

attribute_type: ListBooleanKnapsack
attribute_type_cls

alias of ListBooleanKnapsack

mutate(solution: KnapsackSolution) → tuple[KnapsackSolution, LocalMove][source]
mutate_and_compute_obj(solution: KnapsackSolution) → tuple[KnapsackSolution, LocalMove, dict[str, float]][source]
problem: KnapsackProblem
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: AllocationProblem[Item, bool]

evaluate(variable: 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_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.

Useful to find automatically available mutations for local search. Used by genetic algorithms Ga and Nsga.

This needs only to be implemented in child classes when GA or LS solvers are to be used.

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

get_dummy_solution() → KnapsackSolution[source]

Create a trivial solution for the problem.

Should satisfy the problem ideally. Does not exist for all kind of problems.

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(variable: 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.

property tasks_list: list[Item]

List of all tasks to schedule or allocate to.

property unary_resources_list: list[bool]

Available unary resources.

It can correspond to employees (rcpsp-multiskill), teams (workforce-scheduling), or a mix of several types.

class discrete_optimization.knapsack.problem.KnapsackSolution(problem: KnapsackProblem, list_taken: list[int], value: float | None = None, weight: float | None = None)[source]

Bases: AllocationSolution[Item, bool]

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. It should be implemented in child classes when caching subresults depending on the problem.

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.

is_allocated(task: Item, unary_resource: bool) → bool[source]

Return the usage of the unary resource for the given task.

Parameters:

  • task

  • unary_resource

Returns:

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

problem: KnapsackProblem
class discrete_optimization.knapsack.problem.ListBooleanKnapsack(length: int)[source]

Bases: ListBoolean

Attribute type for boolean list in KnapsackSolution.

This is used to map solution attribute to knapsack-specific mutations in the mutation catalog

class discrete_optimization.knapsack.problem.MobjKnapsackModel(list_items: list[Item], max_capacity: float, force_recompute_values: bool = False)[source]

Bases: KnapsackProblem

evaluate(variable: 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(variable: 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]

Create a trivial solution for the problem.

Should satisfy the problem ideally. Does not exist for all kind of problems.

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(variable: 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_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.

Useful to find automatically available mutations for local search. Used by genetic algorithms Ga and Nsga.

This needs only to be implemented in child classes when GA or LS solvers are to be used.

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

get_dummy_solution() → MultidimensionalKnapsackSolution[source]

Create a trivial solution for the problem.

Should satisfy the problem ideally. Does not exist for all kind of problems.

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(variable: 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. It should be implemented in child classes when caching subresults depending on the problem.

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

problem: MultidimensionalKnapsackProblem | MultiScenarioMultidimensionalKnapsackProblem
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)[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