Set Packing API Reference
Data
Data model for SetPacking use case.
SetPackingData
Bases: UcData
Data for the Set Packing Problem.
Given a universe of elements, a collection of subsets, and weights per subset, the Set Packing problem asks to find the maximum-weight collection of pairwise disjoint subsets.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['set_packing']
|
Identifier for this data type. |
subset_matrix |
list[list[int]]
|
A matrix where each row represents a subset and each column an element. subset_matrix[i][j] = 1 if subset i contains element j, 0 otherwise. |
weights |
list[float]
|
Weight (value) associated with each subset. |
plot(*, ax: Axes | None = None) -> Axes
Plot the subset matrix as a binary heatmap with weights.
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(subset_matrix: list[list[int]], weights: list[float]) -> SetPackingData
staticmethod
Create a SetPackingData instance from explicit values.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
subset_matrix
|
list[list[int]]
|
A matrix where each row represents a subset and each column an element. subset_matrix[i][j] = 1 if subset i contains element j, 0 otherwise. |
required |
weights
|
list[float]
|
Weight (value) associated with each subset. |
required |
Returns:
| Type | Description |
|---|---|
SetPackingData
|
A SetPackingData instance with the given values. |
generate_random(n_elements: int = 5, n_subsets: int = 8, density: float = 0.3, seed: int | None = None) -> SetPackingData
staticmethod
Generate a random set packing instance.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n_elements
|
int
|
Number of elements in the universe, by default 5. |
5
|
n_subsets
|
int
|
Number of subsets, by default 8. |
8
|
density
|
float
|
Probability that an element is included in a subset, by default 0.3. |
0.3
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
SetPackingData
|
A randomly generated set packing instance. |
Formulation
Formulation for SetPacking use case.
SetPackingFormulation
Bases: UcFormulation[SetPackingData, SetPackingSolution]
Constraint-based formulation for the Set Packing Problem.
Mathematical Formulation
Decision Variables: x_s in {0,1} for each subset s: 1 if subset s is selected
Objective: maximize sum_s weights[s] * x_s
Constraints: For each element e: sum_{s containing e} x_s <= 1 (each element can be in at most one selected subset)
to_string(data: SetPackingData) -> str
staticmethod
Return a string describing the formulation.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
SetPackingData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
str
|
String representation of the formulation. |
formulate(data: SetPackingData) -> Model
staticmethod
Formulate the Set Packing Problem using constraint-based approach.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
SetPackingData
|
The Set Packing instance data. |
required |
Returns:
| Type | Description |
|---|---|
Model
|
A Luna Model ready to be solved. |
interpret(solution: Solution, data: SetPackingData) -> SetPackingSolution
staticmethod
Extract solution from quantum result.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The quantum solution. |
required |
data
|
SetPackingData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
SetPackingSolution
|
Structured solution with metrics. |
Solution
Solution model for SetPacking use case.
SetPackingSolution
Bases: UcSolution
Solution for the Set Packing Problem.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['set_packing']
|
Identifier for this solution type. |
selected_subsets |
list[int]
|
Indices of selected subsets. |
total_weight |
float
|
Total weight of selected subsets. |
is_valid |
bool
|
Whether selected subsets are pairwise disjoint. |
plot(data: SetPackingData | None = None, *, ax: Axes | None = None) -> Axes
Plot the set packing solution.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
SetPackingData | 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 SetPacking use case.
SetPackingInstance
Bases: UcInstance[SetPackingData, SetPackingFormulation, SetPackingSolution]
Instance combining data and formulation for SetPacking.
Collection
Collection of SetPacking instances.
SetPackingCollection
Bases: UcInstanceCollection[SetPackingInstance]
Collection of Set Packing instances.
This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.
from_random(min_num_elements: int, max_num_elements: int, num_instances: int = 1, *, density: float = 0.3, subset_ratio: float = 1.6, seed: int | None = None) -> SetPackingCollection
classmethod
Generate random set packing instances.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
min_num_elements
|
int
|
Minimum number of elements per instance. |
required |
max_num_elements
|
int
|
Maximum number of elements per instance. |
required |
num_instances
|
int
|
Number of instances per size, by default 1. |
1
|
density
|
float
|
Probability that an element is included in a subset, by default 0.3. |
0.3
|
subset_ratio
|
float
|
Ratio of subsets to elements, by default 1.6. |
1.6
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
SetPackingCollection
|
Collection containing generated instances. |