Number Partitioning Example

Download Notebook

The Number Partitioning problem divides a set of integers into two subsets such that the difference of their sums is minimized. It is NP-hard and has applications in task scheduling and fair division.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.number_partitioning import (
    NumberPartitioningCollection,
    NumberPartitioningData,
    NumberPartitioningFormulation,
    NumberPartitioningInstance,
)

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 7 integers to partition into two subsets with equal (or closest) sums.

data = NumberPartitioningData.from_values(numbers=[7, 5, 3, 2, 8, 4, 1])
data = NumberPartitioningData.generate_random(8)
print(data.to_string())

Number Partitioning Problem:
  Numbers: [11  3 12  7  1 13 16  8]
  Total sum: 71
  Number count: 8

Plot Data

Visualize the number distribution.

data.plot()

<Axes: title={'center': 'Number Partitioning -- Numbers'}, xlabel='Index', ylabel='Value'>

Create Formulation

Minimize the difference between the two subset sums.

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

Number Partitioning Formulation:
  Numbers: 8
  Total sum S: 71

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 7
  x[i] = 1 if number i is in partition 1
  Total: 8 binary variables

Objective:
  minimize (2 * sum_i n[i] * x[i] - S)^2  where S = 71
  Expanded: sum_{{i,j}} n[i] * n[j] * x[i] * x[j] - S * sum_i n[i] * x[i]

Constraints:
  None (unconstrained binary optimization)

Create Instance

Combine data and formulation into a solvable instance.

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

Data:Number Partitioning Problem:
  Numbers: [11  3 12  7  1 13 16  8]
  Total sum: 71
  Number count: 8
Formulation:Number Partitioning Formulation:
  Numbers: 8
  Total sum S: 71

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 7
  x[i] = 1 if number i is in partition 1
  Total: 8 binary variables

Objective:
  minimize (2 * sum_i n[i] * x[i] - S)^2  where S = 71
  Expanded: sum_{{i,j}} n[i] * n[j] * x[i] * x[j] - S * sum_i n[i] * x[i]

Constraints:
  None (unconstrained binary optimization)

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

Number Partitioning Solution:
  Partition 0: [11, 3, 12, 1, 8] (sum=35)
  Partition 1: [7, 13, 16] (sum=36)
  Difference: 1
  Valid (perfect partition): False

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'Number Partitioning Solution -- difference=1'}, ylabel='Sum'>

Collections

Generate a benchmark collection of random instances for batch processing.

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

Model: number_partitioning<s42_n5_i0>
Minimize
  12 * x_0 * x_1 + 24 * x_0 * x_2 + 60 * x_0 * x_3 + 30 * x_0 * x_4
  + 16 * x_1 * x_2 + 40 * x_1 * x_3 + 20 * x_1 * x_4 + 80 * x_2 * x_3
  + 40 * x_2 * x_4 + 100 * x_3 * x_4 - 63 * x_0 - 44 * x_1 - 80 * x_2
  - 140 * x_3 - 95 * x_4
Binary
  x_0 x_1 x_2 x_3 x_4