Skip to content

Subset Sum Example

Download Notebook

The Subset Sum problem asks whether a subset of integers sums to a specified target. It is NP-complete and one of the fundamental problems in cryptography and computational complexity.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.subset_sum import (
    SubsetSumCollection,
    SubsetSumData,
    SubsetSumFormulation,
    SubsetSumInstance,
)

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 6 integers and a target sum of 14.
Alternatively, generate a random set with a feasible target

data = SubsetSumData(numbers=[3, 7, 1, 8, 5, 2], target=14)
data = SubsetSumData.generate_random(6)
print(data.to_string())

Subset Sum Problem:
  Numbers: [ 6 10  2  5  8  3]
  Target: 27
  Total sum: 34
  Number count: 6

Plot Data

Visualize the numbers and target.

data.plot()


<Axes: title={'center': 'Subset Sum -- Numbers'}, xlabel='Index', ylabel='Value'>
png

Create Formulation

Find a subset of numbers that sums exactly to the target.

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

Subset Sum Formulation:
  Numbers: 6
  Target: 27

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 5
  x[i] = 1 if number i is selected
  Total: 6 binary variables

Objective:
  minimize 0 (feasibility problem)

Constraints:
  1. Sum equals target (1 constraint):
     sum_i numbers[i] * x[i] == 27

Create Instance

Combine data and formulation into a solvable instance.

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

Data:Subset Sum Problem:
  Numbers: [ 6 10  2  5  8  3]
  Target: 27
  Total sum: 34
  Number count: 6
Formulation:Subset Sum Formulation:
  Numbers: 6
  Target: 27

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 5
  x[i] = 1 if number i is selected
  Total: 6 binary variables

Objective:
  minimize 0 (feasibility problem)

Constraints:
  1. Sum equals target (1 constraint):
     sum_i numbers[i] * x[i] == 27

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')













Subset Sum Solution:
  Selected indices: [0 1 4 5]
  Selected sum: 27
  Difference from target: 0
  Valid (sum == target): True



Plot Solution


Visualize the optimal solution.


uc_solution.plot(data)



<Axes: title={'center': 'Subset Sum Solution -- sum=27'}, xlabel='Index', ylabel='Value'>


png


Collections


Generate a benchmark collection of random instances for batch processing.


collection = SubsetSumCollection.from_random(
    min_n_numbers=5,
    max_n_numbers=8,
    seed=42,
)
model = collection.instances[0].formulate()
print(model)



Model: subset_sum<subset_sum>
Minimize

Subject To
  sum_equals_target: 3 * x_0 + 2 * x_1 + 4 * x_2 + 10 * x_3 + 5 * x_4 == 13
Binary
  x_0 x_1 x_2 x_3 x_4