Skip to content

quast_decisiontree.problems.classes.qubo

quast_decisiontree.problems.classes.qubo

General QUBO problem

QUBO

Bases: OptimizationProblem

class representing an instance of a general quadratic unconstrained binary optimization problem

Source code in src/quast_decisiontree/problems/classes/qubo.py 
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
class QUBO(OptimizationProblem):
    """class representing an instance of a general quadratic unconstrained binary optimization
    problem
    """

    direct_encoding_modes = ("QUBO",)
    alias = ["QUBO"]
    matrix_modes = ["symmetric", "upper_triangular", "raw"]
    coeff_tol = 1e-5

    def __init__(self, qubo_matrix: np.ndarray, matrix_mode: str = "symmetric") -> None:
        """initializes a qubo instance

        Params:
            qubo_matrix (np.ndarray): the QUBO matrix of the instance
            matrix_mode (str): A str indicating the form of the matrix stored in the instance.
                Options are:
                    - "symmetric" (default): symmetrize the QUBO matrix
                    - "upper_triangular": turn it into an upper triangular matrix
                    - "raw": allow any kind of QUBO matrix
        """
        self.matrix_mode = matrix_mode
        self.qubo_matrix = qubo_matrix

    @property
    def qubo_matrix(self):
        return self._qubo_matrix

    @qubo_matrix.setter
    def qubo_matrix(self, qubo):
        arr = np.asarray(qubo)
        if arr.ndim != 2 or arr.shape[0] != arr.shape[1]:
            raise ValueError(f"QUBO matrix is not square, but has shape {arr.shape}")
        if not np.issubdtype(arr.dtype, np.number):
            raise ValueError(f"QUBO matrix must be numeric, got dtype {arr.dtype!r}.")

        self._qubo_matrix = np.array(arr)
        self._remedy_qubo_matrix()

    def _remedy_qubo_matrix(self):
        if self.matrix_mode == "symmetric":
            self._qubo_matrix = 1 / 2 * (self._qubo_matrix + self._qubo_matrix.T)
        if self.matrix_mode == "upper_triangular":
            self._qubo_matrix = np.triu(self._qubo_matrix + self._qubo_matrix.T) - np.diag(
                np.diag(self._qubo_matrix)
            )

    @property
    def num_nodes(self):
        return np.shape(self.qubo_matrix)[0]

    @property
    def matrix_mode(self):
        return self._matrix_mode

    @matrix_mode.setter
    def matrix_mode(self, val):
        old_mode = getattr(self, "_matrix_mode", None)

        if val is None:
            val = self.matrix_modes[0]
        val = val.lower()
        if val not in self.matrix_modes:
            raise ValueError(f"Cannot set invalid matrix mode {val!r}.")
        self._matrix_mode = val

        if old_mode is not None and old_mode != val:
            self._remedy_qubo_matrix()

    @classmethod
    def create_random_instance(
        cls,
        size: int,
        seed: Any = None,
        min_coeff: float = 0,
        max_coeff: float = 10,
        density: float = 1,
        negative_diag: bool = True,
        int_coeffs: bool = False,
        matrix_mode: str = "symmetric",
    ):
        """create a random QUBO instance.
        Parameters:
            size (int) : How many variables are contained in the QUBO
            seed (Any) : seed passed on to the random numbers generator
            min_coeff (float): lower bound of the coefficients drawn randomly. Default 0.
            max_coeff (float): upper bound of the coefficients drawn randomly. Default 10.
            density (float): If between 0 and 1, sets the (mean) density of the off-diagonal
                components.
                Values larger than 1 are treated as 1, values smaller than 0 will result in a
                diagonal QUBO (that is, a  trivial binary linear problem). Default 1.
            negative_diag (bool): whether the diagonal should be drawn from the interval
                (-max_coeff, -min_coeff). Default True.
            int_coeffs (bool): whether the coeffs should be integer. Default False.
            matrix_mode (str): a matrix mode from QUBO.matrix_modes to be passed to the
                constructor of the instance. Since the random numbers generated are upper
                triangular, there is no difference between 'raw' and 'upper_triangular'
                modes.

        Returns:
            a randomly created QUBO instance
        """
        rng = rd.default_rng(seed)

        if int_coeffs:
            diag = rng.integers(int(min_coeff), int(max_coeff), size, endpoint=True)
            basic_coeffs = rng.integers(
                int(min_coeff), int(max_coeff), (size, size), endpoint=True
            )
        else:
            diag = rng.uniform(min_coeff, max_coeff, size)
            basic_coeffs = rng.uniform(min_coeff, max_coeff, (size, size))
        if negative_diag:
            diag = -diag
        basic_coeffs = np.triu(basic_coeffs)

        density = min(1, density)
        density = max(0, density)
        mask = rng.binomial(1, density, (size, size))

        qubo = basic_coeffs * mask
        np.fill_diagonal(qubo, diag)
        return cls(qubo, matrix_mode=matrix_mode)

    @classmethod
    def from_dict(cls, problem_dict: Mapping):
        """constructs the QUBO from dict.

        Raises:
            InvalidProblemDictError: If the required 'qubo_matrix' key is missing.
        """
        try:
            qubo_matrix = problem_dict["qubo_matrix"]
        except KeyError as exc:
            raise InvalidProblemDictError(
                "QUBO problem dict is missing required key 'qubo_matrix'."
            ) from exc
        matrix_mode = problem_dict.get("matrix_mode", cls.matrix_modes[0])
        return cls(qubo_matrix, matrix_mode=matrix_mode)

    def __eq__(self, other: object) -> bool:
        """checks whether the QUBOs are equal.

        Permutations of variables is not recognized as equal.
        """
        if not isinstance(other, QUBO):
            return NotImplemented
        if np.shape(self.qubo_matrix) != np.shape(other.qubo_matrix):
            return False
        return bool(
            np.all(
                np.abs(
                    (self.qubo_matrix + self.qubo_matrix.T)
                    - (other.qubo_matrix + other.qubo_matrix.T)
                )
                < 2 * self.coeff_tol
            )
        )

    def to_dict(self) -> dict:
        """converts the QUBO instance to a dictionary.

        Returns:
            dict: A dictionary. Content:
            "problem_class" : "QUBO"
            "qubo_matrix": the QUBO matrix
            "matrix_mode": the stored matrix mode
        """
        return {
            "problem_class": "QUBO",
            "qubo_matrix": self.qubo_matrix.tolist(),
            "matrix_mode": self.matrix_mode,
        }

    def evaluate_objective(self, result: list | str) -> float:
        if isinstance(result, str):
            result = bitstring_to_list(result)

        result = np.array(result)
        return np.linalg.multi_dot([result, self.qubo_matrix, result])

    def formulate_problem(self, mode: str = "QUBO") -> tuple[float, np.ndarray]:
        self._check_mode_support(mode)
        return 0, self.qubo_matrix

direct_encoding_modes class-attribute instance-attribute 

direct_encoding_modes = ('QUBO',)

alias class-attribute instance-attribute 

alias = ['QUBO']

matrix_modes class-attribute instance-attribute 

matrix_modes = ['symmetric', 'upper_triangular', 'raw']

coeff_tol class-attribute instance-attribute 

coeff_tol = 1e-05

qubo_matrix property writable 

qubo_matrix

num_nodes property 

num_nodes

matrix_mode property writable 

matrix_mode

__init__ 

__init__(qubo_matrix, matrix_mode='symmetric')

initializes a qubo instance

Parameters:

Name Type Description Default
qubo_matrix ndarray

the QUBO matrix of the instance

 required
matrix_mode str

A str indicating the form of the matrix stored in the instance. Options are: - "symmetric" (default): symmetrize the QUBO matrix - "upper_triangular": turn it into an upper triangular matrix - "raw": allow any kind of QUBO matrix

 'symmetric'
Source code in src/quast_decisiontree/problems/classes/qubo.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
def __init__(self, qubo_matrix: np.ndarray, matrix_mode: str = "symmetric") -> None:
    """initializes a qubo instance

    Params:
        qubo_matrix (np.ndarray): the QUBO matrix of the instance
        matrix_mode (str): A str indicating the form of the matrix stored in the instance.
            Options are:
                - "symmetric" (default): symmetrize the QUBO matrix
                - "upper_triangular": turn it into an upper triangular matrix
                - "raw": allow any kind of QUBO matrix
    """
    self.matrix_mode = matrix_mode
    self.qubo_matrix = qubo_matrix

create_random_instance classmethod 

create_random_instance(
    size,
    seed=None,
    min_coeff=0,
    max_coeff=10,
    density=1,
    negative_diag=True,
    int_coeffs=False,
    matrix_mode="symmetric",
)

create a random QUBO instance. Parameters: size (int) : How many variables are contained in the QUBO seed (Any) : seed passed on to the random numbers generator min_coeff (float): lower bound of the coefficients drawn randomly. Default 0. max_coeff (float): upper bound of the coefficients drawn randomly. Default 10. density (float): If between 0 and 1, sets the (mean) density of the off-diagonal components. Values larger than 1 are treated as 1, values smaller than 0 will result in a diagonal QUBO (that is, a trivial binary linear problem). Default 1. negative_diag (bool): whether the diagonal should be drawn from the interval (-max_coeff, -min_coeff). Default True. int_coeffs (bool): whether the coeffs should be integer. Default False. matrix_mode (str): a matrix mode from QUBO.matrix_modes to be passed to the constructor of the instance. Since the random numbers generated are upper triangular, there is no difference between 'raw' and 'upper_triangular' modes.

Returns:

Type Description

a randomly created QUBO instance
Source code in src/quast_decisiontree/problems/classes/qubo.py 
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
@classmethod
def create_random_instance(
    cls,
    size: int,
    seed: Any = None,
    min_coeff: float = 0,
    max_coeff: float = 10,
    density: float = 1,
    negative_diag: bool = True,
    int_coeffs: bool = False,
    matrix_mode: str = "symmetric",
):
    """create a random QUBO instance.
    Parameters:
        size (int) : How many variables are contained in the QUBO
        seed (Any) : seed passed on to the random numbers generator
        min_coeff (float): lower bound of the coefficients drawn randomly. Default 0.
        max_coeff (float): upper bound of the coefficients drawn randomly. Default 10.
        density (float): If between 0 and 1, sets the (mean) density of the off-diagonal
            components.
            Values larger than 1 are treated as 1, values smaller than 0 will result in a
            diagonal QUBO (that is, a  trivial binary linear problem). Default 1.
        negative_diag (bool): whether the diagonal should be drawn from the interval
            (-max_coeff, -min_coeff). Default True.
        int_coeffs (bool): whether the coeffs should be integer. Default False.
        matrix_mode (str): a matrix mode from QUBO.matrix_modes to be passed to the
            constructor of the instance. Since the random numbers generated are upper
            triangular, there is no difference between 'raw' and 'upper_triangular'
            modes.

    Returns:
        a randomly created QUBO instance
    """
    rng = rd.default_rng(seed)

    if int_coeffs:
        diag = rng.integers(int(min_coeff), int(max_coeff), size, endpoint=True)
        basic_coeffs = rng.integers(
            int(min_coeff), int(max_coeff), (size, size), endpoint=True
        )
    else:
        diag = rng.uniform(min_coeff, max_coeff, size)
        basic_coeffs = rng.uniform(min_coeff, max_coeff, (size, size))
    if negative_diag:
        diag = -diag
    basic_coeffs = np.triu(basic_coeffs)

    density = min(1, density)
    density = max(0, density)
    mask = rng.binomial(1, density, (size, size))

    qubo = basic_coeffs * mask
    np.fill_diagonal(qubo, diag)
    return cls(qubo, matrix_mode=matrix_mode)

from_dict classmethod 

from_dict(problem_dict)

constructs the QUBO from dict.

Raises:

Type Description
InvalidProblemDictError

If the required 'qubo_matrix' key is missing.
Source code in src/quast_decisiontree/problems/classes/qubo.py 
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
@classmethod
def from_dict(cls, problem_dict: Mapping):
    """constructs the QUBO from dict.

    Raises:
        InvalidProblemDictError: If the required 'qubo_matrix' key is missing.
    """
    try:
        qubo_matrix = problem_dict["qubo_matrix"]
    except KeyError as exc:
        raise InvalidProblemDictError(
            "QUBO problem dict is missing required key 'qubo_matrix'."
        ) from exc
    matrix_mode = problem_dict.get("matrix_mode", cls.matrix_modes[0])
    return cls(qubo_matrix, matrix_mode=matrix_mode)

__eq__ 

__eq__(other)

checks whether the QUBOs are equal.

Permutations of variables is not recognized as equal.

Source code in src/quast_decisiontree/problems/classes/qubo.py 
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
def __eq__(self, other: object) -> bool:
    """checks whether the QUBOs are equal.

    Permutations of variables is not recognized as equal.
    """
    if not isinstance(other, QUBO):
        return NotImplemented
    if np.shape(self.qubo_matrix) != np.shape(other.qubo_matrix):
        return False
    return bool(
        np.all(
            np.abs(
                (self.qubo_matrix + self.qubo_matrix.T)
                - (other.qubo_matrix + other.qubo_matrix.T)
            )
            < 2 * self.coeff_tol
        )
    )

to_dict 

to_dict()

converts the QUBO instance to a dictionary.

Returns:

Name Type Description
dict dict

A dictionary. Content:
dict

"problem_class" : "QUBO"
dict

"qubo_matrix": the QUBO matrix
dict

"matrix_mode": the stored matrix mode
Source code in src/quast_decisiontree/problems/classes/qubo.py 
181
182
183
184
185
186
187
188
189
190
191
192
193
194
def to_dict(self) -> dict:
    """converts the QUBO instance to a dictionary.

    Returns:
        dict: A dictionary. Content:
        "problem_class" : "QUBO"
        "qubo_matrix": the QUBO matrix
        "matrix_mode": the stored matrix mode
    """
    return {
        "problem_class": "QUBO",
        "qubo_matrix": self.qubo_matrix.tolist(),
        "matrix_mode": self.matrix_mode,
    }

evaluate_objective 

evaluate_objective(result)
Source code in src/quast_decisiontree/problems/classes/qubo.py 
196
197
198
199
200
201
def evaluate_objective(self, result: list | str) -> float:
    if isinstance(result, str):
        result = bitstring_to_list(result)

    result = np.array(result)
    return np.linalg.multi_dot([result, self.qubo_matrix, result])

formulate_problem 

formulate_problem(mode='QUBO')
Source code in src/quast_decisiontree/problems/classes/qubo.py 
203
204
205
def formulate_problem(self, mode: str = "QUBO") -> tuple[float, np.ndarray]:
    self._check_mode_support(mode)
    return 0, self.qubo_matrix