Set Packing Example

Download Notebook

The Set Packing problem asks for the maximum-weight collection of pairwise disjoint subsets. It is NP-hard and arises in resource allocation and auction design.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.set_packing import (
    SetPackingCollection,
    SetPackingData,
    SetPackingFormulation,
    SetPackingInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define 4 subsets over 5 elements with weights. Packed subsets must not overlap.

subset_matrix = [
    [1, 1, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 1, 1],
]
weights = [3.0, 5.0, 2.0, 4.0]
data = SetPackingData.from_values(subset_matrix=subset_matrix, weights=weights)
print(data.to_string())

Set Packing Problem:
  Number of elements: 5
  Number of subsets: 4
  Subset 0: elements [0, 1], weight=3.0
  Subset 1: elements [2, 3], weight=5.0
  Subset 2: elements [1, 2], weight=2.0
  Subset 3: elements [3, 4], weight=4.0

Plot Data

Visualize subset-element membership and weights.

data.plot()

<Axes: title={'center': 'Set Packing -- Subset Matrix'}, xlabel='Element j', ylabel='Subset i'>

Create Formulation

Select the maximum-weight collection of non-overlapping subsets.

formulation = SetPackingFormulation()
print(formulation.to_string(data))

Set Packing Formulation:
  Subsets: 4
  Elements: 5

Decision Variables:
  x[s] in {0,1} for s = 0, ..., 3
  x[s] = 1 if subset s is selected
  Total: 4 binary variables

Objective:
  maximize sum_s weights[s] * x[s]

Constraints:
  1. Each element in at most one selected subset (5 constraints):
     sum_{s containing e} x[s] <= 1  for all e = 0, ..., 4

Create Instance

Combine data and formulation into a solvable instance.

instance = SetPackingInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Set Packing Problem:
  Number of elements: 5
  Number of subsets: 4
  Subset 0: elements [0, 1], weight=3.0
  Subset 1: elements [2, 3], weight=5.0
  Subset 2: elements [1, 2], weight=2.0
  Subset 3: elements [3, 4], weight=4.0
Formulation:Set Packing Formulation:
  Subsets: 4
  Elements: 5

Decision Variables:
  x[s] in {0,1} for s = 0, ..., 3
  x[s] = 1 if subset s is selected
  Total: 4 binary variables

Objective:
  maximize sum_s weights[s] * x[s]

Constraints:
  1. Each element in at most one selected subset (5 constraints):
     sum_{s containing e} x[s] <= 1  for all e = 0, ..., 4

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

2026-05-29 11:35:56 INFO     Sleeping for 5.0 seconds. Waiting and checking a function in a loop.

Set Packing Solution:
  Selected subsets: [0, 1]
  Total weight: 8.0
  Valid (pairwise disjoint): True

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'Set Packing Solution -- 2 subsets, weight=8.0'}, xlabel='Element j', ylabel='Subset i'>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = SetPackingCollection.from_random(min_num_elements=5, max_num_elements=8, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: set_packing<set_packing>
Maximize
  8.183533968086616 * x_0 + 2.4404287410820023 * x_1 + 8.180211390760853 * x_2
  + 3.2837051501295167 * x_3 + 1.4949538834777854 * x_4
  + 4.965159840571039 * x_5 + 7.429598555002906 * x_6 + 1.6326353709135477 * x_7
Subject To
  packing_element_0: x_0 + x_1 + x_2 + x_4 <= 1
  packing_element_1: x_1 + x_2 + x_3 + x_4 + x_5 + x_6 <= 1
  packing_element_2: x_0 + x_3 + x_5 <= 1
  packing_element_3: x_3 <= 1
  packing_element_4: x_7 <= 1
Binary
  x_0 x_1 x_2 x_3 x_4 x_5 x_6 x_7