Skip to content

Set Partitioning API Reference

Data

Data model for SetPartitioning use case.

SetPartitioningData

Bases: UcData

Data for the Set Partitioning Problem.

Given a universe of elements, a collection of subsets, and costs per subset, the Set Partitioning problem asks to find a minimum-cost collection of subsets such that every element is covered exactly once.

Attributes:

Name Type Description
name Literal['set_partitioning']

Identifier for this data type.
subset_matrix NumPyArray

A 2D NumPy array (int) where each row represents a subset and each column an element. subset_matrix[i][j] = 1 if subset i contains element j, 0 otherwise.
costs NumPyArray

A 1D NumPy array (float) with costs associated with each subset.

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

Plot the subset matrix as a binary heatmap with costs.

Parameters:

Name Type Description Default
ax Axes | None

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

 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]], costs: list[float]) -> SetPartitioningData staticmethod

Create a SetPartitioningData instance from explicit values.

Parameters:

Name Type Description Default
subset_matrix NumPyArray

A list of integers 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
costs NumPyArray

Costs associated with each subset.

 required

Returns:

Type Description
SetPartitioningData

A SetPartitioningData instance with the given values.

generate_random(n_elements: int = 5, n_subsets: int = 8, density: float = 0.4, seed: int | None = None, costs_generation: Literal['random', 'proportional'] = 'random') -> SetPartitioningData staticmethod

Generate a random set partitioning 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.4.

 0.4
seed int | None

Random seed for reproducibility, by default None.

 None
costs_generation Literal['random', 'proportional']

Cost generation strategy. "random" draws from Uniform(1, 10), "proportional" sets costs to subset size +/- Uniform(-0.5, 1.0), by default "random".

 'random'

Returns:

Type Description
SetPartitioningData

A randomly generated set partitioning instance.

Formulation

Formulation for SetPartitioning use case.

SetPartitioningFormulation

Bases: UcFormulation[SetPartitioningData, SetPartitioningSolution]

Constraint-based formulation for the Set Partitioning Problem.

Mathematical Formulation 
Decision Variables:
    x_s in {0,1} for each subset s: 1 if subset s is selected

Objective:
    minimize sum_s costs[s] * x_s

Constraints:
    For each element e:
        sum_{s containing e} x_s == 1
    (each element must be covered exactly once)

to_string(data: SetPartitioningData) -> str staticmethod

Return a string describing the formulation.

Parameters:

Name Type Description Default
data SetPartitioningData

The problem data.

 required

Returns:

Type Description
str

String representation of the formulation.

formulate(data: SetPartitioningData) -> Model staticmethod

Formulate the Set Partitioning Problem using constraint-based approach.

Parameters:

Name Type Description Default
data SetPartitioningData

The Set Partitioning instance data.

 required

Returns:

Type Description
Model

A LunaModel ready to be solved.

interpret(solution: Solution, data: SetPartitioningData) -> SetPartitioningSolution staticmethod

Extract solution from quantum result.

Parameters:

Name Type Description Default
solution Solution

The quantum solution.

 required
data SetPartitioningData

The problem data.

 required

Returns:

Type Description
SetPartitioningSolution

Structured solution with metrics.

Solution

Solution model for SetPartitioning use case.

SetPartitioningSolution

Bases: UcSolution

Solution for the Set Partitioning Problem.

Attributes:

Name Type Description
name Literal['set_partitioning']

Identifier for this solution type.
selected_subsets list[int]

Indices of selected subsets.
total_cost float

Total cost of selected subsets.
is_valid bool

Whether each element is covered exactly once.

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

Plot the set partitioning solution.

Parameters:

Name Type Description Default
data SetPartitioningData | None

Problem data for context.

 None
ax Axes | None

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

 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 SetPartitioning use case.

SetPartitioningInstance

Bases: UcInstance[SetPartitioningData, SetPartitioningFormulation, SetPartitioningSolution]

Instance combining data and formulation for SetPartitioning.

Collection

Collection of SetPartitioning instances.

SetPartitioningCollection

Bases: UcInstanceCollection[SetPartitioningInstance]

Collection of Set Partitioning instances.

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

from_random(min_num_elements: int | None = None, max_num_elements: int | None = None, num_instances: int = 1, *, sizes: Sequence[int] | None = None, density: float = 0.4, subset_ratio: float = 1.6, costs_generation: Literal['proportional', 'random'] = 'random', seed: int | None = None) -> SetPartitioningCollection classmethod

Generate random set partitioning instances.

Parameters:

Name Type Description Default
min_num_elements int | None

Minimum number of elements per instance.

 None
max_num_elements int | None

Maximum number of elements per instance.

 None
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.4.

 0.4
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
sizes Sequence[int] | None

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

 None

Returns:

Type Description
SetPartitioningCollection

Collection containing generated instances.

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:

Name Type Description Default
max_runtime float

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

 3600
quiet bool

Suppress the SCIP solver output.

 True

Returns:

Type Description
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:

Type Description
ValueError

If max_runtime is not positive.