Skip to content

Graph Partitioning Example

Download Notebook

Graph Partitioning divides the nodes of a graph into equal-sized groups while minimizing the number of edges crossing between them. Applications include parallel computing, VLSI design, and load balancing.

import getpass
import os

import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.graph_partitioning import (
    GraphPartitioningCollection,
    GraphPartitioningData,
    GraphPartitioningFormulation,
    GraphPartitioningInstance,
)

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 a 5-node weighted graph to partition into two balanced groups.

adj = np.array(
    [
        [0.0, 3.5, 2.1, 0.0, 0.0],
        [3.5, 0.0, 1.8, 4.2, 0.0],
        [2.1, 1.8, 0.0, 0.0, 5.0],
        [0.0, 4.2, 0.0, 0.0, 2.7],
        [0.0, 0.0, 5.0, 2.7, 0.0],
    ]
)
node_names = ["A", "B", "C", "D", "E"]
data = GraphPartitioningData.from_adjacency_matrix(adjacency_matrix=adj, node_names=node_names)
print(data.to_string())

Graph Partitioning Data:
  Nodes: 5
  Edges: 6

Plot Data

Visualize the graph structure.

data.plot()


<Axes: title={'center': 'Graph Partitioning — 5 nodes, 6 edges'}>
png

Create Formulation

Minimize edges between the two partitions while keeping group sizes balanced.

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

Graph Partitioning Formulation:
  Nodes: 5
  Edges: 6

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 4
  x[i] = 1 if node i is in partition 1, else partition 0
  Total: 5 binary variables

Objective:
  minimize sum_False w_ij * (x[i] + x[j] - 2*x[i]*x[j])

Constraints:
  1. Equal partition size (1 constraint): n // 2 = 5 // 2 = 2
     sum_i x[i] == 2

Create Instance

Combine data and formulation into a solvable instance.

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

Data:Graph Partitioning Data:
  Nodes: 5
  Edges: 6
Formulation:Graph Partitioning Formulation:
  Nodes: 5
  Edges: 6

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 4
  x[i] = 1 if node i is in partition 1, else partition 0
  Total: 5 binary variables

Objective:
  minimize sum_False w_ij * (x[i] + x[j] - 2*x[i]*x[j])

Constraints:
  1. Equal partition size (1 constraint): n // 2 = 5 // 2 = 2
     sum_i x[i] == 2

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:34:28 INFO     Sleeping for 5.0 seconds. Waiting and checking a function in a loop.










Graph Partitioning Solution:
  Cut edges: 3
  Cut weight: 6.60
  Valid: False
  Partition 0: ['A', 'B', 'D']
  Partition 1: ['C', 'E']



Plot Solution


Visualize the optimal solution.


uc_solution.plot(data)



<Axes: title={'center': 'Graph Partitioning — cut edges=3, cut weight=6.60, valid=False'}>


png


Collections


Generate a benchmark collection of random instances for batch processing.


collection = GraphPartitioningCollection.from_random(
    min_nodes=4,
    max_nodes=8,
    num_instances=2,
    seed=42,
)
model = collection.instances[0].formulate()
print(model)



Model: graph_partitioning<graph_partitioning>
Minimize
  -7.7169311943291845 * x_0 * x_1 - 15.806703573466757 * x_0 * x_2
  - 2.074404104780533 * x_1 * x_2 + 11.76181738389797 * x_0
  + 4.895667649554859 * x_1 + 8.940553839123645 * x_2
Subject To
  equal_partition: x_0 + x_1 + x_2 + x_3 == 2
Binary
  x_0 x_1 x_2 x_3