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 | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
to_string() -> str
Return a string describing the data.
Returns:
| Type | Description |
|---|---|
str
|
String representation of the data. |
from_values(numbers: list[int], target: int) -> SubsetSumData
staticmethod
Create a SubsetSumData instance from explicit values.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
numbers
|
list[int]
|
A list of integers to choose from. |
required |
target
|
int
|
The target sum to achieve. |
required |
Returns:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
n_numbers
|
int
|
Number of integers, by default 10. |
10
|
max_value
|
int | None
|
Maximum value for each integer, by default None and will be set to 2 time n_number. |
None
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
SubsetSumData
|
A randomly generated subset sum instance. |
Raises:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
SubsetSumData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
str
|
String representation of the formulation. |
formulate(data: SubsetSumData) -> Model
staticmethod
Formulate the Subset Sum Problem using constraint-based approach.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
SubsetSumData
|
The Subset Sum instance data. |
required |
Returns:
| Type | Description |
|---|---|
Model
|
A Luna Model ready to be solved. |
interpret(solution: Solution, data: SubsetSumData) -> SubsetSumSolution
staticmethod
Extract solution from result.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The solution. |
required |
data
|
SubsetSumData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
SubsetSumSolution
|
Structured solution with metrics. |
Solution
Solution model for SubsetSum use case.
SubsetSumSolution
Bases: UcSolution
Solution for the Subset Sum Problem.
Attributes:
| Name | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
SubsetSumData | None
|
Problem data for context. |
None
|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
to_string() -> str
Return a string describing the solution.
Returns:
| Type | Description |
|---|---|
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, max_n_numbers: int, num_instances: int = 1, *, max_value: int | None = None, seed: int | None = None) -> SubsetSumCollection
classmethod
Generate random subset sum instances.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
min_n_numbers
|
int
|
Minimum number of integers per instance. |
required |
max_n_numbers
|
int
|
Maximum number of integers per instance. |
required |
num_instances
|
int
|
Number of instances per size, by default 1. |
1
|
max_value
|
int | None
|
Maximum value for each integer, by default None. |
None
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
SubsetSumCollection
|
Collection containing generated instances. |