Source code for eqc_models.combinatorics.setcover

r"""
SetCoverModel solves the mathematical programming problem
$$
\mathrm{minimize}_x \sum_{x_i:X_i \in X} c_i x_i
$$
Subject to
$$
\sum_{i:a\in X_i} x_j \geq 1 \, \forall a \in A}
$$$
and 
$$
x_i \in \{0, 1\} \forall {x_i: X_i \in X}
$$
Where $S$ is a set of all elements, $X$ is a collection of sets $X_i$, and the union of all is equal to $S$. 
"""
from typing import List
import numpy as np
from eqc_models.base import ConstrainedQuadraticModel
[docs]
class SetCoverModel(ConstrainedQuadraticModel):
    """
    Parameters
    -------------
    subsets : List
        List of sets where the union of all sets is S
    weights : List
        List of weights where each weight is the cost of choosing the subset
        corresponding to the index of the weight.
    >>> X = [set(['A', 'B']), set(['B', 'C']), set(['C'])]
    >>> weights = [2, 2, 1]
    >>> model = SetCoverModel(X, weights)
    >>> model.penalty_multiplier = 8
    >>> lhs, rhs = model.constraints
    >>> lhs
    array([[ 1,  0,  0,  0,  0],
           [ 1,  1,  0, -1,  0],
           [ 0,  1,  1,  0, -1]])
    >>> from eqc_models.solvers import Dirac3IntegerCloudSolver
    >>> solver = Dirac3IntegerCloudSolver()
    >>> response = solver.solve(model, relaxation_schedule=1, num_samples=5) #doctest: +ELLIPSIS
    20...
    >>> solutions = response["results"]["solutions"]
    >>> solutions[0]
    [1, 0, 1, 0, 0]
    >>> selections = model.decode(solutions[0])
    >>> assert {'B', 'A'} in selections
    >>> assert {'C'} in selections
    >>> assert len(selections) == 2
    """
    def __init__(self, subsets, weights):
        # ensure that X is ordered
        self.S = S = list(subsets)
        self.universal_set = U = set()
        for x in subsets:
            U.update(x)
        # elements is sorted to maintain consistent output
        elements = [a for a in U]
        elements.sort()
        # constraints 
        A = []
        b = []
        variables = [f'x_{i}' for i in range(len(S))]
        pos = 0
        num_slacks = 0
        slack_ub = []
        for a in elements:
            num_sets = sum([1 if a in S[i] else 0 for i in range(len(S))])
            assert num_sets >= 1, "Invalid subsets, check the universal set"
            if num_sets > 1:
                num_slacks += 1
            slack_ub.append(num_sets-1)
        for i, a in enumerate(elements):
            constraint = [1 if a in S[j] else 0 for j in range(len(S))]
            slacks = [0 for i in range(num_slacks)]
            if slack_ub[i] > 0:
                variables.append(f"s_{pos}")
                slacks[pos] = -1
                pos += 1
            A.append(constraint + slacks)
            b.append(1)
        n = len(variables)
        J = np.zeros((n, n))
        h = np.zeros((n, ))
        h[:len(weights)] = weights
        # call the superclass constructor with the objective and constraints
        super(SetCoverModel, self).__init__(h, J, np.array(A), np.array(b))
        # set upper bound on the variables to be 1 for x_i and the length of X minus 1 for the slacks
        slack_ub = [val for val in slack_ub if val > 0]
        self.upper_bound = np.array([1 for i in range(len(weights))] + slack_ub)
[docs]
    def decode(self, solution) -> List:
        xbar = []
        for i in range(len(self.S)):
            if solution[i] > 0.5:
                xbar.append(self.S[i])
        return xbar