Skip to content

Minimum Set Cover

MinSetCover 

MinSetCover(
    universe: list,
    subsets: list,
    subset_weights: list = None,
    solver_options: dict = {},
)

This class solves the minimum set cover problem. Given a universe universe and a list of subsets subsets, the goal is to find the minimum-weight list of subsets set_cover such that:

  • every element in universe is in at least one subset in set_cover.
  • the sum of the weights of the subsets in set_cover is minimized.

Parameters

  • universe: list

    The universe of elements that must be covered.

  • subsets: list

    A list of subsets that can be used to cover the universe.

  • subset_weights: list

    The weight of each subset, as a list in the same order that the subsets appear in the list subsets. If not provided, each subset is assumed to have a weight of 1.

  • solver_options : dict, optional

    Dictionary with the solver options. Default is {}. See solver options documentation.

Source code in flowpaths/minsetcover.py 
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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
def __init__(
    self,
    universe: list,
    subsets: list,
    subset_weights: list = None,
    solver_options: dict = {},
    ):
    """
    This class solves the minimum set cover problem. Given a universe `universe` and a list of subsets `subsets`,
    the goal is to find the minimum-weight list of subsets `set_cover` such that: 

    - every element in `universe` is in at least one subset in `set_cover`.
    - the sum of the weights of the subsets in `set_cover` is minimized.

    Parameters
    ----------

    - `universe: list`

        The universe of elements that must be covered.

    - `subsets: list`

        A list of subsets that can be used to cover the universe.

    - `subset_weights: list`

        The weight of each subset, as a list in the same order that the subsets appear in the list `subsets`. 
        If not provided, each subset is assumed to have a weight of 1.

    - `solver_options : dict`, optional

        Dictionary with the solver options. Default is `{}`. See [solver options documentation](solver-options-optimizations.md).
    """

    self.universe = universe
    self.subsets = subsets
    self.subset_weights = subset_weights
    self.set_cover = []
    self.set_cover_indices = []
    self.set_cover_weights = []
    self.solver_options = solver_options

    self.__is_solved = None
    self.__solution = None

    self.__encode_set_cover()

get_solution 

get_solution(
    as_subsets: bool = False,
)

Returns the solution to the minimum generating set problem, if the model was solved.

Parameters

  • as_subsets: bool

    If True, returns the subsets themselves. If False, returns the indices of the subsets in the list subsets.

Warning

Call the solve method first.

Source code in flowpaths/minsetcover.py 
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
def get_solution(self, as_subsets: bool = False):
    """
    Returns the solution to the minimum generating set problem, if the model was solved. 

    Parameters
    ----------
    - `as_subsets: bool`

        If `True`, returns the subsets themselves. If `False`, returns the indices of the subsets in the list `subsets`.

    !!! warning "Warning"
        Call the `solve` method first.
    """
    if self.__solution is not None:
        if not as_subsets:
            return self.__solution
        else:
            return [self.subsets[i] for i in self.__solution]

    self.check_is_solved()

is_solved 

is_solved()

Returns True if the model was solved, False otherwise.

Source code in flowpaths/minsetcover.py 
118
119
120
121
122
123
124
125
126
def is_solved(self):
    """
    Returns `True` if the model was solved, `False` otherwise.
    """
    if self.__is_solved is None:
        self.solver.logger.error(f"{__name__}: Model not yet solved. If you want to solve it, call the `solve` method first.")
        raise Exception("Model not yet solved. If you want to solve it, call the `solve` method first.")

    return self.__is_solved

solve 

solve() -> bool

Solves the minimum set cover problem.

Returns

  • bool

    True if the model was solved, False otherwise.

Source code in flowpaths/minsetcover.py 
 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
def solve(self) -> bool:
    """
    Solves the minimum set cover problem. 

    Returns
    -------
    - bool

        `True` if the model was solved, `False` otherwise.
    """
    start_time = time.perf_counter()

    self.solver.optimize()
    if self.solver.get_model_status() == "kOptimal":
        subset_cover_sol = self.solver.get_variable_values("subset", [int])
        self.__solution = [i for i in range(len(self.subsets)) if subset_cover_sol[i] == 1]
        self.__is_solved = True
        self.solve_statistics = {
            "solve_time": time.perf_counter() - start_time,
            "num_elements": len(self.__solution),
            "status": self.solver.get_model_status(),
        }
        return True
    else:
        self.solve_statistics = {
            "solve_time": time.perf_counter() - start_time,
            "status": self.solver.get_model_status(),
        }
        return False