Source code for eqc_models.combinatorics.setpartition

from typing import List, Tuple, Dict, Union
import numpy as np
from eqc_models.base import ConstraintsMixIn, PolynomialModel
from eqc_models.base.polynomial import ConstrainedPolynomialModel
[docs]
class SetPartitionModel(ConstrainedPolynomialModel):
    """
    This class represents a set partitioning model for optimization problems that require selecting subsets
    to partition a universal set while minimizing an objective function defined by weights. Given a collection
    of subsets, a weight is assigned to each subset, and the goal is to determine an optimal selection of subsets
    to fully cover the universal set with minimized total weight.
    Parameters
    ----------
    subsets : List of sets
        List of sets (subsets) defining the collection to partition.
        Each element in this list represents a subset containing elements from the universal set.
    weights : List of floats
        List of weights corresponding to each subset. The length of this list should be equal to
        the number of subsets, with each weight indicating the cost or weight associated with selecting
        a particular subset.
    Attributes
    ----------
    H : tuple of np.ndarray
        Tuple containing the linear (h) and quadratic (J) coefficients for the Hamiltonian representation
        of the quadratic problem formulation.
    penalty_multiplier : float
        Value for weighting the penalties formed from the equality constraints.
    polynomial : Polynomial
        Polynomial operator representation for the model, constructed from the penalty terms
        to encode the set partition constraints.
    linear_objective : np.ndarray
        Array representing the linear objective function coefficients based on the weights of subsets.
    quad_objective : np.ndarray
        Quadratic objective function matrix initialized as zeros (no quadratic terms for objective).
    constraints : tuple of np.ndarray
        Matrix `A` and vector `b` representing constraints for the set partition problem:
        - `A`: Binary matrix indicating subset membership of elements in the universal set.
        - `b`: Vector of ones, enforcing full coverage of the universal set by the selected subsets.
    universal_set : set
        Set containing all unique elements present across the input subsets, representing the elements
        that must be fully covered in the partition solution.
    Example
    --------
    Given a list of subsets representing a set partition problem, each with an associated weight:
    >>> import numpy as np
    >>> np.random.seed(21)
    >>> subsets = [{"A", "B", "C"}, {"D", "E", "F"}, {"A", "F"}, {"B", "E"}, {"C", "D"}, {"A"},
                   {"B"}, {"C", "D", "E"}, {"B", "C"}]
    >>> weights = [100 * np.random.random() for _ in subsets]
    We can construct and use the `SetPartitionModel` as follows:
    >>> model = SetPartitionModel(subsets=subsets, weights=weights)
    >>> solution = np.random.randint(0, 2, len(subsets))  # Random binary solution vector
    >>> print("Objective Value:", model.evaluateObjective(solution))  # Evaluate solution cost
    This approach builds the constraints matrix and penalties automatically, enabling efficient
    optimization using solvers like `Dirac3CloudSolver`.
    """
    def __init__(self, subsets: List[set], weights: List[float]) -> None:
        # Combine subsets to form the universal set
        self.universal_set = set()
        for subset in subsets:
            self.universal_set = self.universal_set.union(subset)
        # Create the constraint matrix A and vector b
        A = []
        for x in self.universal_set:
            row = [1 if x in subset else 0 for subset in subsets]
            A.append(row)
        A = np.array(A)
        b = np.ones((A.shape[0],))
        n = A.shape[1]
        self.upper_bound = np.ones((n,), np.int32)
        # Define the linear objective function based on subset weights
        self.linear_objective = np.array(weights).reshape((n, 1))
        self.quad_objective = np.zeros((n, n)) #np.zeros_like(J)
        # Initialize PolynomialModel with J and h, properly formatted as indices and coefficients
        indices, coefficients = self._construct_polynomial_terms(self.linear_objective, self.quad_objective)
        super().__init__(coefficients, indices, A, b)
    def _construct_polynomial_terms(self, h: np.ndarray, J: np.ndarray) -> Tuple[List[List[int]], List[np.ndarray]]:
        """
        Constructs the polynomial terms (indices and coefficients) needed for the quadratic
        Hamiltonian representation of the problem.
        Parameters
        ----------
        h : np.ndarray
            Linear term of the penalty function as a 1D array.
        J : np.ndarray
            Quadratic term of the penalty function as a 2D array.
        Returns
        -------
        Tuple[List[List[int]], List[float]]
            A tuple where:
            - The first element is a list of index lists, representing terms in polynomial format.
            - The second element is a list of float coefficients corresponding to each term.
        """
        indices = []
        coefficients = []
        # Linear terms
        for i in range(h.shape[0]):
            if h[i, 0] != 0:
                indices.append([0, i + 1])  # 1-based index
                coefficients.append(h[i, 0])
        # Quadratic terms
        for i in range(J.shape[0]):
            for j in range(i, J.shape[1]):
                if J[i, j] != 0:
                    indices.append([i + 1, j + 1])  # 1-based indices
                    coefficients.append(J[i, j])
        return indices, coefficients
[docs]
    def evaluateObjective(self, solution: np.ndarray) -> float:
        """
        Evaluate the objective function by calculating the weighted sum of selected subsets.
        Parameters
        ----------
        solution : np.ndarray
            Binary array where each element indicates if a subset is selected (1) or not (0).
        Returns
        -------
        float
            The value of the objective function, representing the total weight of selected subsets.
        """
        return float(np.squeeze(solution).T @ np.squeeze(self.linear_objective))