Repository: dwavesystems/dimod
Pull request #1390 (2024-09-20 17:10:53)

Multiple Knapsack Generator
A multiple knapsack generator that allows for custom values, weights, and capacities to be passed in instead of randomly generating these values.

Updated the old `random_multi_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.

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/dwavesystems/dimod/pull/1390?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dwavesystems) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 94.86%. Comparing base [(`9b17267`)](https://app.codecov.io/gh/dwavesystems/dimod/commit/9b17267e2db2db0f0687e63741db05ed6ca6df14?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dwavesystems) to head [(`837a71b`)](https://app.codecov.io/gh/dwavesystems/dimod/commit/837a71b2809be690a374cc4ca87ccee01375717b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dwavesystems).

<details><summary>Additional details and impacted files</summary>


```diff
@@           Coverage Diff           @@
##             main    #1390   +/-   ##
=======================================
  Coverage   94.85%   94.86%           
=======================================
  Files          98       98           
  Lines       10447    10455    +8     
=======================================
+ Hits         9910     9918    +8     
  Misses        537      537           
```

| [Flag](https://app.codecov.io/gh/dwavesystems/dimod/pull/1390/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dwavesystems) | Coverage Δ | |
|---|---|---|
| [](https://app.codecov.io/gh/dwavesystems/dimod/pull/1390/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dwavesystems) | `94.86% <100.00%> (?)` | |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dwavesystems#carryforward-flags-in-the-pull-request-comment) to find out more.

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/dwavesystems/dimod/pull/1390?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dwavesystems).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dwavesystems).


Patch:
diff --git a/dimod/generators/multi_knapsack.py b/dimod/generators/multi_knapsack.py
index c9584dd3..f6756678 100644
--- a/dimod/generators/multi_knapsack.py
+++ b/dimod/generators/multi_knapsack.py
@@ -12,13 +12,68 @@
 #    See the License for the specific language governing permissions and
 #    limitations under the License.
 
+from typing import Tuple
+
 import numpy as np
 
 from dimod.binary_quadratic_model import BinaryQuadraticModel
 from dimod.constrained import ConstrainedQuadraticModel
-from typing import Tuple
+from dimod.typing import ArrayLike
+
+__all__ = ['multi_knapsack', 'random_multi_knapsack']
+
+
+def multi_knapsack(values: ArrayLike,
+                   weights: ArrayLike,
+                   capacities: ArrayLike,
+                   ) -> ConstrainedQuadraticModel:
+    """Generate a constrained quadratic model encoding a multiple knapsack problem.
+
+    The multiple knapsack problem seeks to fit the most value into each knapsack
+    of weight less than or equal to each knapsack's 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.
+        capacities: A list of the maximum weights each knapsack can hold.
+
+    Returns:
+
+        A constrained quadratic model encoding the multiple-knapsack problem.
+        Variables are labelled as ``x_{i}_{j}``, where ``x_{i}_{j} == 1`` means
+        that item ``i`` is placed in bin ``j``.
+
+    """
+    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 = {(i, j): obj.add_variable(f'x_{i}_{j}') for i in range(values.shape[0]) for j in range(len(capacities))}
+
+    for i, value in enumerate(values):
+        for j in range(len(capacities)):
+            obj.set_linear(x[(i, j)], -value)
+
+    model.set_objective(obj)
 
-__all__ = ['random_multi_knapsack']
+    # Each item at most goes to one bin.
+    for i in range(values.shape[0]):
+        model.add_constraint(
+            [(x[(i, j)], 1) for j in range(len(capacities))] + [(-1,)],
+            sense="<=", label='item_placing_{}'.format(i))
+
+    # Build knapsack capacity constraints
+    for j, capacity in enumerate(capacities):
+        model.add_constraint(
+            [(x[(i, j)], weight) for i, weight in enumerate(weights)] + [(-capacity,)],
+            sense="<=", label='capacity_bin_{}'.format(j))
+
+    return model
 
 
 def random_multi_knapsack(num_items: int,
@@ -37,13 +92,9 @@ def random_multi_knapsack(num_items: int,
 
     Args:
         num_items: Number of items.
-
         num_bins: Number of bins.
-
-        seed: Seed for RNG.
-
+        seed: Seed for 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.
 
     Returns:
@@ -54,35 +105,15 @@ def random_multi_knapsack(num_items: int,
 
     """
 
-    rng = np.random.RandomState(seed)
+    rng = np.random.default_rng(seed)
 
-    weights = rng.randint(*weight_range, num_items)
-    values = rng.randint(*value_range, num_items)
+    values = rng.integers(*value_range, num_items)
+    weights = rng.integers(*weight_range, num_items)
 
     cap_low = int(weight_range[0] * num_items / num_bins)
     cap_high = int(weight_range[1] * num_items / num_bins)
-    capacities = rng.randint(cap_low, cap_high, num_bins)
+    capacities = rng.integers(cap_low, cap_high, num_bins)
 
-    model = ConstrainedQuadraticModel()
-
-    obj = BinaryQuadraticModel(vartype='BINARY')
-    x = {(i, j): obj.add_variable(f'x_{i}_{j}') for i in range(num_items) for j in range(num_bins)}
-
-    for i in range(num_items):
-        for j in range(num_bins):
-            obj.set_linear(x[(i, j)], -values[i])
-
-    model.set_objective(obj)
-
-    # Each item at most goes to one bin.
-    for i in range(num_items):
-        model.add_constraint([(x[(i, j)], 1) for j in range(num_bins)] + [(-1,)], sense="<=",
-                             label='item_placing_{}'.format(i))
-
-    # Build knapsack capacity constraints
-    for j in range(num_bins):
-        model.add_constraint(
-            [(x[(i, j)], weights[i]) for i in range(num_items)] + [(-capacities[j],)],
-            sense="<=", label='capacity_bin_{}'.format(j))
+    model = multi_knapsack(values, weights, capacities)
 
     return model
diff --git a/docs/reference/generators.rst b/docs/reference/generators.rst
index 0c460820..aad9b4dc 100644
--- a/docs/reference/generators.rst
+++ b/docs/reference/generators.rst
@@ -50,6 +50,7 @@ Optimization
    maximum_independent_set
    maximum_weight_independent_set
    mimo
+   multi_knapsack
    quadratic_assignment
    random_bin_packing
    random_knapsack
diff --git a/releasenotes/notes/multi-knapsack-generator-cf29619dec749a1a.yaml b/releasenotes/notes/multi-knapsack-generator-cf29619dec749a1a.yaml
new file mode 100644
index 00000000..eb3f6ab7
--- /dev/null
+++ b/releasenotes/notes/multi-knapsack-generator-cf29619dec749a1a.yaml
@@ -0,0 +1,4 @@
+---
+features:
+  - |
+    Add ``multi_knapsack`` generator function to ``dimod.generators``.


Test patch:
diff --git a/tests/test_generators.py b/tests/test_generators.py
index a3c3110d..5d68f343 100644
--- a/tests/test_generators.py
+++ b/tests/test_generators.py
@@ -599,6 +599,10 @@ class TestBinPacking(unittest.TestCase):
 
 class TestMultiKnapsack(unittest.TestCase):
 
+    def test_exceptions(self):
+        with self.assertRaises(ValueError):
+            dimod.generators.multi_knapsack([1], [], [])
+
     def test_model(self):
         num_items = 20
         num_bins = 10