Skip to content

Subset Sum API Reference

Data

Data model for SubsetSum use case.

SubsetSumData

Bases: UcData

Data for the Subset Sum Problem.

Given a set of integers and a target value, the Subset Sum problem asks whether there exists a subset whose elements sum to the target.

Attributes:

  • name (Literal['subset_sum']) –

    Identifier for this data type.

  • numbers (NumPyArray) –

    A 1D NumPy array containing the integers to choose from.

  • target (int) –

    The target sum to achieve.

plot(*, ax: Axes | None = None) -> Axes

Plot the numbers as a bar chart with target line.

Parameters:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the data.

Returns:

  • str –

    String representation of the data.

from_values(numbers: list[int], target: int) -> SubsetSumData staticmethod

Create a SubsetSumData instance from explicit values.

Parameters:

  • numbers (list[int]) –

    A list of integers to choose from.

  • target (int) –

    The target sum to achieve.

Returns:

  • SubsetSumData –

    A SubsetSumData instance with the given values.

generate_random(n_numbers: int = 10, max_value: int | None = None, seed: int | None = None) -> SubsetSumData staticmethod

Generate a random subset sum instance.

Generates random numbers and picks a valid target as the sum of a random subset, ensuring the problem is feasible.

Parameters:

  • n_numbers (int, default: 10 ) –

    Number of integers, by default 10.

  • max_value (int | None, default: None ) –

    Maximum value for each integer, by default None and will be set to 2 time n_number.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

Raises:

  • ValueError –

    If n_numbers > max_value, which makes distinct sampling impossible.

Formulation

Formulation for SubsetSum use case.

SubsetSumFormulation

Bases: UcFormulation[SubsetSumData, SubsetSumSolution]

Constraint-based formulation for the Subset Sum Problem.

Mathematical Formulation 
Decision Variables:
    x_i in {0,1} for each number i: 1 if number i is selected

Objective:
    minimize 0 (feasibility problem)

Constraints:
    sum_i numbers[i] * x_i == target

to_string(data: SubsetSumData) -> str staticmethod

Return a string describing the formulation.

Parameters:

Returns:

  • str –

    String representation of the formulation.

formulate(data: SubsetSumData) -> Model staticmethod

Formulate the Subset Sum Problem using constraint-based approach.

Parameters:

Returns:

  • Model –

    A LunaModel ready to be solved.

interpret(solution: Solution, data: SubsetSumData) -> SubsetSumSolution staticmethod

Extract solution from result.

Parameters:

  • solution (Solution) –

    The solution.

  • data (SubsetSumData) –

    The problem data.

Returns:

Solution

Solution model for SubsetSum use case.

SubsetSumSolution

Bases: UcSolution

Solution for the Subset Sum Problem.

Attributes:

  • name (Literal['subset_sum']) –

    Identifier for this solution type.

  • selected_indices (NumPyArray) –

    Indices of selected numbers.

  • selected_sum (int) –

    Sum of selected numbers.

  • difference (int) –

    Absolute difference |sum - target|.

  • is_valid (bool) –

    Whether the selected sum equals the target.

plot(data: SubsetSumData | None = None, *, ax: Axes | None = None) -> Axes

Plot the subset sum solution.

Parameters:

  • data (SubsetSumData | None, default: None ) –

    Problem data for context.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the solution.

Returns:

  • str –

    String representation of the solution.

Instance

Instance model for SubsetSum use case.

SubsetSumInstance

Bases: UcInstance[SubsetSumData, SubsetSumFormulation, SubsetSumSolution]

Instance combining data and formulation for SubsetSum.

Collection

Collection of SubsetSum instances.

SubsetSumCollection

Bases: UcInstanceCollection[SubsetSumInstance]

Collection of Subset Sum instances.

This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.

from_random(min_n_numbers: int | None = None, max_n_numbers: int | None = None, num_instances: int = 1, *, sizes: Sequence[int] | None = None, max_value: int | None = None, seed: int | None = None) -> SubsetSumCollection classmethod

Generate random subset sum instances.

Parameters:

  • min_n_numbers (int | None, default: None ) –

    Minimum number of integers per instance.

  • max_n_numbers (int | None, default: None ) –

    Maximum number of integers per instance.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • max_value (int | None, default: None ) –

    Maximum value for each integer, by default None.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

  • sizes (Sequence[int] | None, default: None ) –

    Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_n_numbers/max_n_numbers, by default None.

Returns:

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

  • max_runtime (float, default: 3600 ) –

    SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • list[bool] –

    Feasibility mask over the instances as they were before filtering, in that order: True where the instance was kept, False where it was removed.

Raises: