knapsack module¶
Knapsack problem.
This module implements the Knapsack problem.
In its simplest form, it states that:
Given a set of items, each with a given weight and value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given weight capacity and the total value is as large as possible.
Multiple variations of the Knapsack problem can be achieved depending on the inputs provided.
Moreover, a multi-objective version of this problem is also available, in which the following new objective function is added to previous formulation:
- class gemseo_pymoo.problems.analytical.knapsack.Knapsack(values, weights, items_ub=None, binary=True, capacity_weight=None, capacity_items=None, initial_guess=None)[source]
Bases:
OptimizationProblem
Generic knapsack optimization problem.
Different variations can be achieved:
0/1 or Binary Knapsack problem:
Given a set of \(n\) items, each with a weight \(w_i\) and a value \(v_i\), and a knapsack with a maximum weight capacity \(W\). Choose which items to pack in order to maximize the total knapsack value while respecting its weight capacity.
Unbounded Knapsack problem:
With respect to the Binary variant, it removes the restriction that there is only one of each item. This can be achieved by setting the attribute
binary
to False, which will remove the upper bound of the design variables.Bounded Knapsack problem:
With respect to the Binary variant, it specifies an upper bound for each item. This can be achieved by providing an array
items_ub
with the upper bound relative to each item.
Moreover, an additional constraint regarding the total number of items can be added. This is achieved through the attribute
capacity_items
and will limit the number of items that fit into the knapsack.The constructor.
Initialize the Knapsack
OptimizationProblem
by defining theDesignSpace
and the objective and constraint functions.The number of items in the problem is deduced from the
values
array.- Parameters:
values (ndarray) – The items’ values.
weights (ndarray) – The items’ weights.
items_ub (ndarray | None) – The items’ upper bounds. If None, an unlimited number of each item is allowed.
binary (bool) –
If True, the upper bound of design variables is set to 1.
By default it is set to True.
capacity_weight (float | None) – The knapsack weight capacity. If None, the knapsack will have an unlimited weight capacity.
capacity_items (int | None) – The knapsack number of items capacity. If None, the knapsack will accept an unlimited total number of items.
initial_guess (ndarray | None) – The initial guess for the optimal solution. If None, the initial guess will be an empty knapsack (0, 0, …, 0).
- Raises:
ValueError – Either if the provided arrays do not have the same length or if no capacity is provided.
- static compute_knapsack_items(design_variables)[source]
Compute the knapsack number of items.
- compute_knapsack_value(design_variables)[source]
Compute the knapsack total value.
- compute_knapsack_weight(design_variables)[source]
Compute the knapsack total weight.
- capacity_items: int
The knapsack number of items capacity.
- capacity_weight: float
The knapsack weight capacity.
- constraints: list[MDOFunction]
The constraints.
- current_iter: int
The current iteration.
- database: Database
The database to store the optimization problem data.
- design_space: DesignSpace
The design space on which the optimization problem is solved.
- eq_tolerance: float
The tolerance for the equality constraints.
- fd_step: float
The finite differences step.
- ineq_tolerance: float
The tolerance for the inequality constraints.
- max_iter: int
The maximum iteration.
- new_iter_observables: list[MDOFunction]
The observables to be called at each new iterate.
- nonproc_constraints: list[MDOFunction]
The non-processed constraints.
- nonproc_new_iter_observables: list[MDOFunction]
The non-processed observables to be called at each new iterate.
- nonproc_objective: MDOFunction
The non-processed objective function.
- nonproc_observables: list[MDOFunction]
The non-processed observables.
- observables: list[MDOFunction]
The observables.
- pb_type: ProblemType
The type of optimization problem.
- preprocess_options: dict
The options to pre-process the functions.
- solution: OptimizationResult
The solution of the optimization problem.
- stop_if_nan: bool
Whether the optimization stops when a function returns
NaN
.
- use_standardized_objective: bool
Whether to use standardized objective for logging and post-processing.
The standardized objective corresponds to the original one expressed as a cost function to minimize. A
DriverLibrary
works with this standardized objective and theDatabase
stores its values. However, for convenience, it may be more relevant to log the expression and the values of the original objective.
- values: ndarray
The knapsack items’ value.
- weights: ndarray
The knapsack items’ weight.
- class gemseo_pymoo.problems.analytical.knapsack.MultiObjectiveKnapsack(values, weights, items_ub=None, binary=True, capacity_weight=None, capacity_items=None, initial_guess=None)[source]
Bases:
Knapsack
Multi-objective Knapsack optimization problem.
With respect to the single-objective
Knapsack
, it adds an objective relative to the number of items packed. Therefore, besides maximizing the total knapsack value, one must also minimize the total number of items.All the variations of the
Knapsack
problem can still be achieved.The constructor.
Initialize the MultiObjectiveKnapsack
OptimizationProblem
by defining theDesignSpace
and the objective and constraint functions.The number of items in the problem is deduced from the
values
array.- Parameters:
values (ndarray) – The items’ values.
weights (ndarray) – The items’ weights.
items_ub (ndarray | None) – The items’ upper bounds. If None, an unlimited number of each item is allowed.
binary (bool) –
If True, the upper bound of design variables is set to 1.
By default it is set to True.
capacity_weight (float | None) – The knapsack weight capacity. If None, the knapsack will have an unlimited weight capacity.
capacity_items (int | None) – The knapsack number of items capacity. If None, the knapsack will accept an unlimited total number of items.
initial_guess (ndarray | None) – The initial guess for the optimal solution. If None, the initial guess will be an empty knapsack (0, 0, …, 0).
- capacity_items: int
The knapsack number of items capacity.
- capacity_weight: float
The knapsack weight capacity.
- constraints: list[MDOFunction]
The constraints.
- current_iter: int
The current iteration.
- database: Database
The database to store the optimization problem data.
- design_space: DesignSpace
The design space on which the optimization problem is solved.
- eq_tolerance: float
The tolerance for the equality constraints.
- fd_step: float
The finite differences step.
- ineq_tolerance: float
The tolerance for the inequality constraints.
- max_iter: int
The maximum iteration.
- new_iter_observables: list[MDOFunction]
The observables to be called at each new iterate.
- nonproc_constraints: list[MDOFunction]
The non-processed constraints.
- nonproc_new_iter_observables: list[MDOFunction]
The non-processed observables to be called at each new iterate.
- nonproc_objective: MDOFunction
The non-processed objective function.
- nonproc_observables: list[MDOFunction]
The non-processed observables.
- observables: list[MDOFunction]
The observables.
- pb_type: ProblemType
The type of optimization problem.
- preprocess_options: dict
The options to pre-process the functions.
- solution: OptimizationResult
The solution of the optimization problem.
- stop_if_nan: bool
Whether the optimization stops when a function returns
NaN
.
- use_standardized_objective: bool
Whether to use standardized objective for logging and post-processing.
The standardized objective corresponds to the original one expressed as a cost function to minimize. A
DriverLibrary
works with this standardized objective and theDatabase
stores its values. However, for convenience, it may be more relevant to log the expression and the values of the original objective.
- values: ndarray
The knapsack items’ value.
- weights: ndarray
The knapsack items’ weight.
- gemseo_pymoo.problems.analytical.knapsack.create_random_knapsack_problem(n_items, capacity_level=0.1, binary=True, obj_variant='single')[source]
Create a random
Knapsack
problem.One can also create a
MultiObjectiveKnapsack
problem by providingobj_variant
= ‘multi’.The value and the weight of the items are integers randomly generated between 1 and 100.
- Parameters:
n_items (int) – The size of the set of items.
capacity_level (float) –
The percentage of the set of items total weight corresponding to the knapsack capacity.
By default it is set to 0.1.
binary (bool) –
If True, only one unit of each item is allowed.
By default it is set to True.
obj_variant (str) –
Single-objective (‘single’) or multi-objective (‘multi’) problem.
By default it is set to “single”.
- Returns:
- An instance of
Knapsack
orMultiObjectiveKnapsack
depending on the
obj_variant
provided.
- An instance of
- Raises:
ValueError – Either if the number of items is not a positive integer or if the capacity_level is outside the range (0, 1).
- Return type:
- gemseo_pymoo.problems.analytical.knapsack.randint(low, high=None, size=None, dtype=int)
Return random integers from low (inclusive) to high (exclusive).
Return random integers from the “discrete uniform” distribution of the specified dtype in the “half-open” interval [low, high). If high is None (the default), then results are from [0, low).
Note
New code should use the ~numpy.random.Generator.integers method of a ~numpy.random.Generator instance instead; please see the Quick Start.
- Parameters:
low (int or array-like of ints) – Lowest (signed) integers to be drawn from the distribution (unless
high=None
, in which case this parameter is one above the highest such integer).high (int or array-like of ints, optional) – If provided, one above the largest (signed) integer to be drawn from the distribution (see above for behavior if
high=None
). If array-like, must contain integer valuessize (int or tuple of ints, optional) – Output shape. If the given shape is, e.g.,
(m, n, k)
, thenm * n * k
samples are drawn. Default is None, in which case a single value is returned.dtype (dtype, optional) –
Desired dtype of the result. Byteorder must be native. The default value is int.
New in version 1.11.0.
- Returns:
out – size-shaped array of random integers from the appropriate distribution, or a single such random int if size not provided.
- Return type:
int or ndarray of ints
See also
random_integers
similar to randint, only for the closed interval [low, high], and 1 is the lowest value if high is omitted.
random.Generator.integers
which should be used for new code.
Examples
>>> np.random.randint(2, size=10) array([1, 0, 0, 0, 1, 1, 0, 0, 1, 0]) # random >>> np.random.randint(1, size=10) array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
Generate a 2 x 4 array of ints between 0 and 4, inclusive:
>>> np.random.randint(5, size=(2, 4)) array([[4, 0, 2, 1], # random [3, 2, 2, 0]])
Generate a 1 x 3 array with 3 different upper bounds
>>> np.random.randint(1, [3, 5, 10]) array([2, 2, 9]) # random
Generate a 1 by 3 array with 3 different lower bounds
>>> np.random.randint([1, 5, 7], 10) array([9, 8, 7]) # random
Generate a 2 by 4 array using broadcasting with dtype of uint8
>>> np.random.randint([1, 3, 5, 7], [[10], [20]], dtype=np.uint8) array([[ 8, 6, 9, 7], # random [ 1, 16, 9, 12]], dtype=uint8)