Set Partitioning Example

Download Notebook

The Set Partition problem asks for a minimum-cost collection of subsets such that every element is covered by exactly one subset. It is central to airline crew scheduling and vehicle routing.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.set_partitioning import (
    SetPartitioningCollection,
    SetPartitioningData,
    SetPartitioningFormulation,
    SetPartitioningInstance,
)

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 5 subsets over 5 elements with costs. Every element must be covered exactly once.

data = SetPartitioningData.generate_random(costs_generation="proportional")
subset_matrix = [
    [1, 1, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1],
    [0, 1, 1, 0, 0],
]
costs = [2.0, 3.0, 1.0, 4.0, 2.5]
data = SetPartitioningData.from_values(subset_matrix=subset_matrix, costs=costs)
print(data.to_string())

Set Partitioning Problem:
  Number of elements: 5
  Number of subsets: 5
  Subset 0: elements [0, 1], cost=2.0
  Subset 1: elements [2, 3], cost=3.0
  Subset 2: elements [4], cost=1.0
  Subset 3: elements [0, 4], cost=4.0
  Subset 4: elements [1, 2], cost=2.5

Plot Data

Visualize subset-element membership and costs.

data.plot()

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

Create Formulation

Select the minimum-cost collection of subsets covering every element exactly once.

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

Set Partitioning Formulation:
  Subsets: 5
  Elements: 5

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

Objective:
  minimize sum_s costs[s] * x[s]

Constraints:
  1. Each element covered exactly once (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 = SetPartitioningInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Set Partitioning Problem:
  Number of elements: 5
  Number of subsets: 5
  Subset 0: elements [0, 1], cost=2.0
  Subset 1: elements [2, 3], cost=3.0
  Subset 2: elements [4], cost=1.0
  Subset 3: elements [0, 4], cost=4.0
  Subset 4: elements [1, 2], cost=2.5
Formulation:Set Partitioning Formulation:
  Subsets: 5
  Elements: 5

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

Objective:
  minimize sum_s costs[s] * x[s]

Constraints:
  1. Each element covered exactly once (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 Partitioning Solution:
  Selected subsets: [0, 1, 2]
  Total cost: 6.0
  Valid (each element covered exactly once): True

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'Set Partitioning Solution -- 3 subsets, cost=6.0'}, xlabel='Element j', ylabel='Subset i'>

Collections

Generate a benchmark collection of random instances for batch processing.

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

Model: set_partitioning<set_partitioning>
Minimize
  4.965159840571039 * x_0 + 7.429598555002906 * x_1 + 1.6326353709135477 * x_2
  + 6.009468132433763 * x_3 + 5.47599876835647 * x_4 + 6.749973549857163 * x_5
  + 4.2442654478596396 * x_6 + 9.018722759345494 * x_7
Subject To
  partition_element_0: x_0 + x_1 + x_2 + x_3 + x_4 + x_7 == 1
  partition_element_1: x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 == 1
  partition_element_2: x_0 + x_3 + x_5 == 1
  partition_element_3: x_2 + x_3 == 1
  partition_element_4: x_1 + x_2 + x_4 + x_5 == 1
Binary
  x_0 x_1 x_2 x_3 x_4 x_5 x_6 x_7