Repository: dwavesystems/dimod
Pull request #1391 (2024-09-24 18:34:53)

Quadratic Knapsack Generator
Add quadratic knapsack generator.

This is my first net new generator so please let me know what can be improved!


Patch:
diff --git a/dimod/generators/knapsack.py b/dimod/generators/knapsack.py
index 59b2b847..531818dc 100644
--- a/dimod/generators/knapsack.py
+++ b/dimod/generators/knapsack.py
@@ -20,7 +20,7 @@ from dimod.binary_quadratic_model import BinaryQuadraticModel
 from dimod.constrained import ConstrainedQuadraticModel
 from dimod.typing import ArrayLike
 
-__all__ = ['knapsack', 'random_knapsack']
+__all__ = ['knapsack', 'quadratic_knapsack', 'random_knapsack']
 
 
 def knapsack(values: ArrayLike,
@@ -65,6 +65,61 @@ def knapsack(values: ArrayLike,
     return model
 
 
+def quadratic_knapsack(
+    values: ArrayLike,
+    weights: ArrayLike,
+    profits: ArrayLike,
+    capacity: float,
+) -> ConstrainedQuadraticModel:
+    """Generates a constrained quadratic model encoding a quadratic knapsack problem.
+
+    The quadratic knapsack problem,
+    `QKP <https://en.wikipedia.org/wiki/Quadratic_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.
+        profits: A matrix where entry (i, j) is the value of adding items i and j together.
+        capacity: The maximum weight a knapsack can hold.
+
+    Returns:
+        A constrained quadratic model encoding the quadratic 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)
+    profits = np.asarray(profits)
+
+    if values.shape != weights.shape:
+        raise ValueError("`values` and `weights` must have the same shape")
+
+    if not np.array_equal(profits, profits.T):
+        raise ValueError("`profits` must be symmetric")
+
+    if values.shape[0] != profits.shape[0]:
+        raise ValueError("`profits` must have an entry for each pair of items")
+
+    model = ConstrainedQuadraticModel()
+    obj = BinaryQuadraticModel(vartype='BINARY')
+    x = [obj.add_variable(f'x_{i}') for i in range(profits.shape[0])]
+
+    for i, value in enumerate(values):
+        obj.set_linear(x[i], -value)
+
+    for i, profit in np.ndenumerate(profits):
+        if i[0] < i[1]:
+            obj.set_quadratic(x[i[0]], x[i[1]], -profit)
+
+    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,
                     seed: typing.Optional[int] = None,
                     value_range: typing.Tuple[int, int] = (10, 30),
diff --git a/docs/reference/generators.rst b/docs/reference/generators.rst
index 0c460820..787fcf63 100644
--- a/docs/reference/generators.rst
+++ b/docs/reference/generators.rst
@@ -51,6 +51,7 @@ Optimization
    maximum_weight_independent_set
    mimo
    quadratic_assignment
+   quadratic_knapsack
    random_bin_packing
    random_knapsack
    random_multi_knapsack
diff --git a/releasenotes/notes/quadratic-knapsack-generator-55cb808252579b38.yaml b/releasenotes/notes/quadratic-knapsack-generator-55cb808252579b38.yaml
new file mode 100644
index 00000000..677abc34
--- /dev/null
+++ b/releasenotes/notes/quadratic-knapsack-generator-55cb808252579b38.yaml
@@ -0,0 +1,4 @@
+---
+features:
+  - |
+    Add ``quadratic_knapsack`` generator function to ``dimod.generators``.


Test patch:
diff --git a/tests/test_generators.py b/tests/test_generators.py
index a3c3110d..17b9e8ed 100644
--- a/tests/test_generators.py
+++ b/tests/test_generators.py
@@ -556,6 +556,49 @@ class TestKnapsack(unittest.TestCase):
         lhs = cqm.constraints['capacity'].lhs.energy(x)
         self.assertLessEqual(lhs, 0)
 
+    def test_quadratic_exceptions(self):
+        with self.assertRaises(ValueError):
+            dimod.generators.quadratic_knapsack([1], [], [], 1)
+
+        with self.assertRaises(ValueError):
+            dimod.generators.quadratic_knapsack([1], [1], [[1, 1]], 1)
+
+        with self.assertRaises(ValueError):
+            dimod.generators.quadratic_knapsack([1], [1], [[1, 1], [1, 1]], 1)
+
+    def test_quadratic_model(self):
+        values = [1, 2]
+        weights = [2, 1]
+        profits = [[1, 2], [2, 1]]
+        capacity = 1
+        cqm = dimod.generators.quadratic_knapsack(values, weights, profits, capacity)
+        self.assertEqual(len(cqm.variables), len(values))
+        self.assertEqual(len(cqm.constraints), 1)
+
+    def test_quadratic_infeasible(self):
+        values = [1, 2]
+        weights = [2, 1]
+        profits = [[1, 2], [2, 1]]
+        capacity = 1
+        cqm = dimod.generators.quadratic_knapsack(values, weights, profits, capacity)
+
+        # create an infeasible state, by selecting all the items
+        x = {i: 1 for i in cqm.variables}
+        lhs = cqm.constraints['capacity'].lhs.energy(x)
+        self.assertGreater(lhs, 0)
+
+    def test_quadratic_feasible(self):
+        values = [1, 2]
+        weights = [2, 1]
+        profits = [[1, 2], [2, 1]]
+        capacity = 1
+        cqm = dimod.generators.quadratic_knapsack(values, weights, profits, capacity)
+
+        # create feasible state, by not selecting any item
+        x = {i: 0 for i in cqm.variables}
+        lhs = cqm.constraints['capacity'].lhs.energy(x)
+        self.assertLessEqual(lhs, 0)
+
 
 class TestBinPacking(unittest.TestCase):