Source code for qlauncher.problems.optimization.knapsack

 1"""This module contains the Knapsack class."""
 2
 3from collections.abc import Sequence
 4from typing import Literal
 5
 6import numpy as np
 7from pyqubo import Array, Binary
 8
 9from qlauncher import models
10from qlauncher.base import Problem
11
12

[docs]
13class Knapsack(Problem):
14    """
15    Class for 0/1 Knapsack Problem.
16
17    This class represents the 0/1 Knapsack problem: maximize the total value of chosen items
18    subject to a capacity constraint on total weight. The class wraps a concrete instance
19    and can be passed into QLauncher.
20    """
21
22    def __init__(self, values: Sequence[int], weights: Sequence[int], capacity: int, instance_name: str = 'unnamed'):
23        if len(values) != len(weights) or len(values) == 0:
24            raise ValueError('values and weights must have the same positive length')
25        if capacity < 0:
26            raise ValueError('capacity must be non-negative')
27        super().__init__((values, weights, capacity), instance_name=instance_name)
28        self.values = values
29        self.weights = weights
30        self.capacity = capacity
31

[docs]
32    @staticmethod
33    def from_preset(instance_name: Literal['default', 'small'], **kwargs) -> 'Knapsack':
34        values, weights, capacity = None, None, None
35        match instance_name:
36            case 'default':
37                values = [9, 6, 7, 5]
38                weights = [6, 4, 5, 3]
39                capacity = 9
40            case 'small':
41                values = [4, 3, 2]
42                weights = [3, 2, 2]
43                capacity = 5
44            case _:
45                raise ValueError(f'Preset f{instance_name} not defined')
46        return Knapsack(values, weights, capacity, instance_name)

47

[docs]
48    def to_bqm(self, penalty_weight: float = 2.0, value_weight: float = 1.0) -> models.BQM:
49        """
50        Returns BQM for Knapsack problem.
51        """
52        size = len(self.values)
53
54        x = Array.create('a_x', shape=size, vartype='BINARY')
55
56        m = 1 if self.capacity == 0 else int(np.ceil(np.log2(self.capacity + 1)))
57        y = Array.create('z_y', shape=m, vartype='BINARY')
58        slack = sum((2**k) * y[k] for k in range(m))
59
60        weight_sum = sum(self.weights[i] * x[i] for i in range(size))
61        penalty = weight_sum + slack - self.capacity
62        penalty *= penalty
63        value_term = sum(self.values[i] * x[i] for i in range(size))
64        H: Binary = penalty_weight * penalty - value_weight * value_term
65        return models.BQM(H.compile())