dimod.generators.random_knapsack

random_knapsack(num_items: int, seed: Optional[int] = None, value_range: Tuple[int, int] = (10, 30), weight_range: Tuple[int, int] = (10, 30), tightness_ratio: float = 0.5) → dimod.constrained.constrained.ConstrainedQuadraticModel[source]

Generates a constrained quadratic model encoding a 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.