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

Returns a Constrained Quadratic Model encoding a knapsack problem.

Given the number of items, the code generates a random knapsack problem, formulated as a Constrained Quadratic model. The capacity of the bin is set to be tightness_ratio times the sum of the weights.

  • num_items – Number of items to choose from.

  • seed – Seed for numpy random number generator.

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

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

  • tightness_ratio – ratio of capacity over sum of weights.


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