Repository: dwavesystems/dimod
Pull request #1386 (2024-08-26 23:13:33)

Knapsack Generator
A knapsack generator that allows for custom values, weights, and capacity to be passed in instead of randomly generating these values.

Updated the old random_knapsack generator to call the new generator and pass in the random values.

Added additional test to check if the shapes of values and weights are equal.


Patch:
diff --git a/dimod/generators/knapsack.py b/dimod/generators/knapsack.py
index 9c14e331..59b2b847 100644
--- a/dimod/generators/knapsack.py
+++ b/dimod/generators/knapsack.py
@@ -18,8 +18,51 @@ import numpy as np
 
 from dimod.binary_quadratic_model import BinaryQuadraticModel
 from dimod.constrained import ConstrainedQuadraticModel
+from dimod.typing import ArrayLike
 
-__all__ = ['random_knapsack']
+__all__ = ['knapsack', 'random_knapsack']
+
+
+def knapsack(values: ArrayLike,
+            weights: ArrayLike,
+            capacity: float,
+            ) -> ConstrainedQuadraticModel:
+    """Generates a constrained quadratic model encoding a knapsack problem.
+
+    The knapsack problem,
+    `KP <https://en.wikipedia.org/wiki/Knapsack_problem>`_,
+    seeks to fit the most value into a knapsack of weight less than or equal to
+    capacity for a given list of items with associated values and weights.
+
+    Args:
+        values: A list of each item's value.
+        weights: A list of each item's associated weight.
+        capacity: The maximum weight a knapsack can hold.
+
+    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.
+
+    """
+    values = np.asarray(values)
+    weights = np.asarray(weights)
+
+    if values.shape != weights.shape:
+        raise ValueError("`values` and `weights` must have the same shape")
+
+    model = ConstrainedQuadraticModel()
+    obj = BinaryQuadraticModel(vartype='BINARY')
+    x = [obj.add_variable(f'x_{i}') for i in range(values.shape[0])]
+
+    for i, value in enumerate(values):
+        obj.set_linear(x[i], -value)
+
+    model.set_objective(obj)
+    constraint = [(x[i], weight) for i, weight in enumerate(weights)] + [(-capacity, )]
+    model.add_constraint(constraint, sense="<=", label='capacity')
+
+    return model
 
 
 def random_knapsack(num_items: int,
@@ -28,7 +71,7 @@ def random_knapsack(num_items: int,
                     weight_range: typing.Tuple[int, int] = (10, 30),
                     tightness_ratio: float = 0.5,
                     ) -> ConstrainedQuadraticModel:
-    """Generates a constrained quadratic model encoding a knapsack problem.
+    """Generates a constrained quadratic model encoding a random knapsack problem.
 
     Given the number of items, generates a random knapsack problem, formulated as
     a :class:`~dimod.ConstrainedQuadraticModel`. The capacity of bins is set
@@ -36,13 +79,9 @@ def random_knapsack(num_items: int,
 
     Args:
         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:
@@ -52,21 +91,12 @@ def random_knapsack(num_items: int,
 
     """
 
-    rng = np.random.RandomState(seed)
-
-    value = {i: rng.randint(*value_range) for i in range(num_items)}
-    weight = {i: rng.randint(*weight_range) for i in range(num_items)}
-    capacity = int(sum(weight.values()) * tightness_ratio)
-
-    model = ConstrainedQuadraticModel()
-    obj = BinaryQuadraticModel(vartype='BINARY')
-    x = {i: obj.add_variable(f'x_{i}') for i in range(num_items)}
+    rng = np.random.default_rng(seed)
 
-    for i in range(num_items):
-        obj.set_linear(x[i], -value[i])
+    values = list(rng.integers(*value_range, num_items))
+    weights = list(rng.integers(*weight_range, num_items))
+    capacity = int(np.sum(weights) * tightness_ratio)
 
-    model.set_objective(obj)
-    constraint = [(x[i], weight[i]) for i in range(num_items)] + [(-capacity, )]
-    model.add_constraint(constraint, sense="<=", label='capacity')
+    model = knapsack(values, weights, capacity)
 
     return model
diff --git a/docs/reference/generators.rst b/docs/reference/generators.rst
index 7bfd12ba..0c460820 100644
--- a/docs/reference/generators.rst
+++ b/docs/reference/generators.rst
@@ -46,6 +46,7 @@ Optimization
    bin_packing
    coordinated_multipoint
    independent_set
+   knapsack
    maximum_independent_set
    maximum_weight_independent_set
    mimo
diff --git a/releasenotes/notes/knapsack-generator-59e48aaaf07cb8ac.yaml b/releasenotes/notes/knapsack-generator-59e48aaaf07cb8ac.yaml
new file mode 100644
index 00000000..f5b01d50
--- /dev/null
+++ b/releasenotes/notes/knapsack-generator-59e48aaaf07cb8ac.yaml
@@ -0,0 +1,4 @@
+---
+features:
+  - |
+    Add ``knapsack`` generator function to ``dimod.generators``.


Test patch:
diff --git a/tests/test_generators.py b/tests/test_generators.py
index ec0af0a4..a3c3110d 100644
--- a/tests/test_generators.py
+++ b/tests/test_generators.py
@@ -528,6 +528,10 @@ class TestDoped(unittest.TestCase):
 
 class TestKnapsack(unittest.TestCase):
 
+    def test_exceptions(self):
+        with self.assertRaises(ValueError):
+            dimod.generators.knapsack([1], [], 1)
+
     def test_model(self):
         num_items = 10
         cqm = dimod.generators.random_knapsack(num_items=num_items)