dimod.generators.random_knapsack#

random_knapsack(num_items: int, seed: int | None = None, value_range: Tuple[int, int] = (10, 30), weight_range: Tuple[int, int] = (10, 30), tightness_ratio: float = 0.5) → ConstrainedQuadraticModel[source]#

Generates a constrained quadratic model encoding a random knapsack problem.

Given the number of items, generates a random knapsack problem, formulated as a ConstrainedQuadraticModel. The capacity of bins is set to be tightness_ratio times the sum of the weights.

Parameters:

  • num_items – Number of items to choose from.

  • seed – Seed for NumPy random number generator.

  • value_range – Range of the randomly generated values for each item.

  • weight_range – Range of the randomly generated weights for each item.

  • tightness_ratio – Ratio of capacity over sum of weights.

Returns:

The quadratic model encoding the knapsack problem. Variables are denoted as x_{i} where x_{i} == 1 means that item i is placed in the knapsack.