Skip to content

Minimum Generating Set

MinGenSet 

MinGenSet(
    numbers: list,
    total,
    weight_type: type = float,
    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.

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.

  • 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.

  • 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.

    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
def __init__(
        self, 
        numbers: list,
        total,
        weight_type: type = float,
        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`.

    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`.

    - `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.

    - `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. 

        !!! 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.lowerbound = lowerbound
    self.partition_constraints = partition_constraints

    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 remove_sums_of_two:
        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 
312
313
314
315
316
317
318
319
320
321
322
323
324
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 
295
296
297
298
299
300
301
302
303
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 
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
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_variable_values("gen_set", [int])
            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