Skip to content

Minimum Generating Set

MinGenSet 

MinGenSet(
    numbers: list,
    total: int | float,
    weight_type: (
        int | float
    ) = float,
    max_multiplicity: int = 1,
    lowerbound: int = 1,
    partition_constraints: list = None,
    remove_complement_values: bool = True,
    remove_sums_of_two: bool = False,
    solver_options: dict = {},
)

This class solves the minimum generating set problem. Given a list of numbers a and a total value total, the goal is to find the smallest list of numbers generating_set such that:

  • the sum of the elements in generating_set equals total, and
  • every element in a can be expressed as the sum of some elements in generating_set.

This class solves a more general problem, in which we are also given max_multiplicity, the maximum number of times each element in generating_set can be used to represent elements in a.

Parameters

  • a : list

    A list of numbers.

  • total : int | float

    The total value that the sum of the elements in the generating set should equal.

  • weight_type : type

    The type of the numbers in generating_set. Default is float. The other option is int.

  • max_multiplicity : int

    The maximum number of times each element in the generating set can be used to represent elements in a. Default is 1.

  • lowerbound : int

    The minimum number of elements in the generating set. Default is 1.

  • partition_constraints : list

    A list of lists, where each inner list is made up of numbers, such that the sum of the numbers in each inner list is equal to total. That is, each inner list is a number partition of total. These constraints are imposed as: - each number in an inner list must be obtained by summing up a subset of numbers in the generating set, and - each number in the generating set must be used exactly once to obtain the numbers in the inner list.

    You cannot set this if max_multiplicity > 1.

  • remove_complement_values : bool

    If True, if a contains both x and total - x, it keeps only the smallest of them. Default is True. This is always correct to do. If say the generating set is \(g_1, g_2, g_3, g_4\), with \(g_1 + g_2 + g_3 + g_4 = total\). If \(x = g_1 + g_3\), then \(total - x = g_2 + g_4\). So \(total - x\) is expressed as a sum of values in the generating set.

  • remove_sums_of_two : bool

    If True, it removes elements from a that are the sum of two other elements in a. Default is False. This is not always correct to do, as it might lead to a smaller generating set. For example, suppose the generating set is \(g_1, g_2, g_3, g_4\), with \(g_1\) different from \(g_4\) Suppose \(x = g_1 + g_2\), \(y = g_1 + g_3\) and \(x+y \in a\). Then \(x+y\) is expressed as \(2 g_1 + g_2 + g_3\), thus it needs repeating \(g_1\) twice. So \(x+y\) cannot be expressed as a sum of elements in the generating set.

    You cannot set this to True if max_multiplicity > 1.

    Note

    Setting this to True always gives a generating set smaller or of the same size (i.e., not larger) as setting it to False. Thus, the size of the former generating set can be used as a lower bound for the size of the latter generating set.

  • solver_options : dict, optional

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

Source code in flowpaths/mingenset.py 
  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
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
def __init__(
        self, 
        numbers: list,
        total: int | float,
        weight_type: int | float = float,
        max_multiplicity: int = 1,
        lowerbound: int = 1,
        partition_constraints: list = None,
        remove_complement_values: bool = True,
        remove_sums_of_two: bool = False,
        solver_options: dict = {}
        ):
    """
    This class solves the minimum generating set problem. Given a list of numbers `a` and a total value `total`, 
    the goal is to find the smallest list of numbers `generating_set` such that:

    - the sum of the elements in `generating_set` equals `total`, and
    - every element in `a` can be expressed as the sum of some elements in `generating_set`.

    This class solves a more general problem, in which we are also given `max_multiplicity`, 
    the maximum number of times each element in `generating_set` can be used to represent elements in `a`.

    Parameters
    ----------

    - `a` : list

        A list of numbers.

    - `total` : int | float

        The total value that the sum of the elements in the generating set should equal.

    - `weight_type` : type

        The type of the numbers in `generating_set`. Default is `float`. The other option is `int`.

    - `max_multiplicity` : int

        The maximum number of times each element in the generating set can be used to represent elements in `a`. Default is 1.

    - `lowerbound` : int

        The minimum number of elements in the generating set. Default is 1.

    - `partition_constraints` : list

        A list of lists, where each inner list is made up of numbers, such that the sum of the numbers in each inner list is equal to `total`.
        That is, each inner list is a number partition of `total`.
        These constraints are imposed as:
        - each number in an inner list must be obtained by summing up a subset of numbers in the generating set, and
        - each number in the generating set must be used exactly once to obtain the numbers in the inner list.

        You cannot set this if `max_multiplicity > 1`.

    - `remove_complement_values` : bool

        If `True`, if `a` contains both `x` and `total - x`, it keeps only the smallest of them. Default is `True`.
        This is always correct to do. If say the generating set is $g_1, g_2, g_3, g_4$, with $g_1 + g_2 + g_3 + g_4 = total$.
        If $x = g_1 + g_3$, then $total - x = g_2 + g_4$. So $total - x$ is expressed as a sum of values in the generating set.

    - `remove_sums_of_two` : bool

        If `True`, it removes elements from `a` that are the sum of two other elements in `a`. Default is `False`.
        This is not always correct to do, as it might lead to a smaller generating set. For example, suppose the generating set is $g_1, g_2, g_3, g_4$, with $g_1$ different from $g_4$ 
        Suppose $x = g_1 + g_2$, $y = g_1 + g_3$ and $x+y \in a$. Then $x+y$ is expressed as $2 g_1 + g_2 + g_3$, 
        thus it needs repeating $g_1$ **twice**. So $x+y$ cannot be expressed as a sum of elements in the generating set. 

        You cannot set this to `True` if `max_multiplicity > 1`.

        !!! note "Note"
            Setting this to `True` always gives a generating set smaller or of the same size (i.e., not larger) as setting it to `False`. 
            Thus, the size of the former generating set can be used as a lower bound for the size of the latter generating set.

    - `solver_options : dict`, optional

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

    self.numbers = list(numbers) # Make a copy of the list
    utils.logger.debug(f"{__name__}: Initial numbers: {self.numbers}")
    self.initial_numbers = numbers
    self.total = total
    utils.logger.debug(f"{__name__}: Generating set sum = {self.total}")
    self.weight_type = weight_type
    self.max_multiplicity = max_multiplicity
    if self.max_multiplicity < 1:
        utils.logger.error(f"{__name__}: `max_multiplicity` must be at least 1.")
        raise ValueError("`max_multiplicity` must be at least 1.")
    self.lowerbound = lowerbound
    self.partition_constraints = partition_constraints
    if self.partition_constraints is not None and self.max_multiplicity > 1:
        utils.logger.error(f"{__name__}: `partition_constraints` is set, but `max_multiplicity > 1`. This is not allowed.")
        raise ValueError("`partition_constraints` is not allowed when `max_multiplicity > 1`.")

    self._is_solved = False
    self._solution = None
    self.solver = None
    self.solve_statistics = {}
    self.solver_options = solver_options

    if self.weight_type not in [int, float]:
        utils.logger.error(f"{__name__}: weight_type must be either `int` or `float`.")
        raise ValueError("weight_type must be either `int` or `float`.")

    if self.partition_constraints is not None:
        if not all(isinstance(constraint, list) for constraint in self.partition_constraints):
            utils.logger.error(f"{__name__}: partition_constraints must be a list of lists.")
            raise ValueError("partition_constraints must be a list of lists.")        
        if not all(sum(constraint) == self.total for constraint in self.partition_constraints):
            utils.logger.error(f"{__name__}: The sum of the numbers inside each subset constraint must equal the total value.")
            raise ValueError("The sum of the numbers inside each subset constraint must equal the total value.")

    if False and remove_sums_of_two:
        if self.max_multiplicity > 1:
            utils.logger.error(f"{__name__}: `remove_sums_of_two` is set to True, but `max_multiplicity > 1`. This is not allowed.")
            raise ValueError("`remove_sums_of_two` is not allowed when `max_multiplicity > 1`.")

        elements_to_remove = set()
        for val1 in self.numbers:
            for val2 in self.numbers:
                if val1 + val2 in self.numbers:
                    elements_to_remove.add(val1 + val2)

        self.numbers = list(set(self.numbers) - elements_to_remove)

    if remove_complement_values:
        elements_to_remove = set()
        for val in self.numbers:
            if total - val in self.numbers and total - val > val:
                elements_to_remove.add(total - val)
            if val == total or val == 0:
                elements_to_remove.add(val)

        self.numbers = list(set(self.numbers) - elements_to_remove)

    utils.logger.debug(f"{__name__}: Numbers after removing values: {self.numbers}")

get_solution 

get_solution()

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

Warning

Call the solve method first.

Source code in flowpaths/mingenset.py 
359
360
361
362
363
364
365
366
367
368
369
370
371
def get_solution(self):
    """
    Returns the solution to the minimum generating set problem, if the model was solved. 

    !!! warning "Warning"
        Call the `solve` method first.
    """
    if self._solution is not None:
        return self._solution

    self.check_is_solved()

    return self._solution

is_solved 

is_solved()

Returns True if the model was solved, False otherwise.

Source code in flowpaths/mingenset.py 
342
343
344
345
346
347
348
349
350
def is_solved(self):
    """
    Returns `True` if the model was solved, `False` otherwise.
    """
    if self._is_solved is None:
        utils.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()

Solves the minimum generating set problem. Returns True if the model was solved, False otherwise.

Source code in flowpaths/mingenset.py 
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
def solve(self):
    """
    Solves the minimum generating set problem. Returns `True` if the model was solved, `False` otherwise.
    """
    start_time = time.perf_counter()

    # Solve for increasing numbers of elements in the generating set
    for k in range(self.lowerbound, max(self.lowerbound+1, len(self.initial_numbers))):
        self._create_solver(k=k)
        self.solver.optimize()

        if self.solver.get_model_status() == "kOptimal":
            genset_sol = self.solver.get_values(self.genset_vars)
            self._solution = sorted(self.weight_type(genset_sol[i]) for i in range(k))
            self._is_solved = True
            self.solve_statistics = {
                "solve_time": time.perf_counter() - start_time,
                "num_elements": k,
                "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