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 = 2
    >>> 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, 0]
    >>> model.decode(solutions[0])
    [{'B', 'A'}, {'C'}]
    """
    def __init__(self, subsets, weights):
        # ensure that X is ordered
        self.X = X = list(subsets)
        self.S = S = set()
        for x in subsets:
            S = S.union(x)
        # elements is sorted to maintain consistent output
        elements = [a for a in S]
        elements.sort()
        # constraints 
        A = []
        b = []
        variables = [f'x_{i}' for i in range(len(X))]
        pos = 0
        for a in elements:
            variables.append(f"s_{pos}")
            constraint = [1 if a in X[i] else 0 for i in range(len(X))]
            slacks = [0 for i in range(len(S))]
            slacks[pos] = -1
            A.append(constraint + slacks)
            pos += 1
            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
        self.upper_bound = np.array([1 for i in range(len(weights))] + [len(X)-1 for i in range(n-len(weights))])
[docs]
    def decode(self, solution) -> List:
        xbar = []
        for i in range(len(self.X)):
            if solution[i] > 0.5:
                xbar.append(self.X[i])
        return xbar