Source code for qiskit_optimization.applications.set_packing

# This code is part of a Qiskit project.
# (C) Copyright IBM 2018, 2023.
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.

"""An application class for the set packing."""

from typing import List, Union, cast

import numpy as np
from import Model

from qiskit_optimization.algorithms import OptimizationResult
from qiskit_optimization.problems.quadratic_program import QuadraticProgram
from qiskit_optimization.translators import from_docplex_mp
from .optimization_application import OptimizationApplication

[docs]class SetPacking(OptimizationApplication): """Optimization application for the "set packing" [1] problem. References: [1]: "Set packing", """ def __init__(self, subsets: List[List[int]]) -> None: """ Args: subsets: A list of subsets """ self._subsets = subsets self._set = [] for sub in self._subsets: self._set.extend(sub) self._set = cast(List, np.unique(self._set))
[docs] def to_quadratic_program(self) -> QuadraticProgram: """Convert a set packing instance into a :class:`~qiskit_optimization.problems.QuadraticProgram` Returns: The :class:`~qiskit_optimization.problems.QuadraticProgram` created from the set packing instance. """ mdl = Model(name="Set packing") x = {i: mdl.binary_var(name=f"x_{i}") for i in range(len(self._subsets))} mdl.maximize(mdl.sum(x[i] for i in x)) for element in self._set: mdl.add_constraint( mdl.sum(x[i] for i, sub in enumerate(self._subsets) if element in sub) <= 1 ) op = from_docplex_mp(mdl) return op
[docs] def interpret(self, result: Union[OptimizationResult, np.ndarray]) -> List[List[int]]: """Interpret a result as a list of subsets Args: result: The calculated result of the problem Returns: A list of subsets whose corresponding variable is 1 """ x = self._result_to_x(result) sub = [] for i, value in enumerate(x): if value: sub.append(self._subsets[i]) return sub