gemseo_pymoo / problems / analytical

Show inherited members

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.

\[\begin{split}\begin{aligned} \text{maximize the total knapsack value } & \sum_{i=1}^{n} value_i * x_i \\ \text{with respect to the design variables }&x_i \\ \text{subject to the general constraints } & \sum_{i=1}^{n} weight_i * x_i \leq capacity_weight\\ & \sum_{i=1}^{n} x_i \leq capacity_items\\ \text{subject to the search domain } & x_i \in \mathbb{N} \end{aligned}\end{split}\]

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:

\[\begin{split}\begin{aligned} \text{minimize the number of items carried } & \sum_{i=1}^{n} x_i \\ \end{aligned}\end{split}\]

class gemseo_pymoo.problems.analytical.knapsack.Knapsack(values, weights, items_ub=None, binary=True, capacity_weight=None, capacity_items=None, initial_guess=None)

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 the DesignSpace 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)

Compute the knapsack number of items.

Parameters:

design_variables (ndarray) – The design variables vector.

Returns:

The knapsack total number of items.

Return type:

ndarray

compute_knapsack_value(design_variables)

Compute the knapsack total value.

Parameters:

design_variables (ndarray) – The design variables vector.

Returns:

The knapsack total value.

Return type:

ndarray

compute_knapsack_weight(design_variables)

Compute the knapsack total weight.

Parameters:

design_variables (ndarray) – The design variables vector.

Returns:

The knapsack total weight.

Return type:

ndarray

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 | None

The solution of the optimization problem if solved; otherwise None.

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 the Database 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)

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 the DesignSpace 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 | None

The solution of the optimization problem if solved; otherwise None.

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 the Database 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')

Create a random Knapsack problem.

One can also create a MultiObjectiveKnapsack problem by providing obj_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 or MultiObjectiveKnapsack depending

on the obj_variant provided.

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:

Knapsack | MultiObjectiveKnapsack