Skip to content

MaxCut Example

Download Notebook

This notebook demonstrates how to use the Maxcut use case.

import getpass
import os

import matplotlib.pyplot as plt
import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.maxcut import (
    MaxcutCollection,
    MaxcutData,
    MaxcutFormulation,
    MaxcutInstance,
)

load_dotenv()

if "LUNA_API_KEY" not in os.environ:
    # Prompt securely for the key if not already set
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define the problem data.

maxcut_data = MaxcutData(
    name="maxcut",
    node_names=["A", "B", "C", "D"],
    adjacency_matrix=np.array([[0, 3, 2, 0], [3, 0, 4, 1], [2, 4, 0, 5], [0, 1, 5, 0]]),
    node_position={"A": (0, 0), "B": (1, 0), "C": (1, 1), "D": (0, 1)},
)

print(maxcut_data.to_string())

MaxCut Data:
  Nodes: 4
  Edges: 5

Plot Data

Visualize the graph with nodes and weighted edges.

ax = maxcut_data.plot()
plt.show()

png

Create Formulation

Define the optimization formulation.

formulation = MaxcutFormulation(name="maxcut")
print(formulation.to_string(maxcut_data))

Maximum Cut (MaxCut) Formulation:
  Nodes: 4
  Edges: 5

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

Objective:
  maximize sum_False w[i,j] * (x[i] + x[j] - 2 * x[i] * x[j])

Constraints:
  None (unconstrained binary optimization)

Create Instance

Combine data and formulation into an instance.

instance = MaxcutInstance(data=maxcut_data, formulation=formulation)
print(instance.to_string())

Data:MaxCut Data:
  Nodes: 4
  Edges: 5
Formulation:Maximum Cut (MaxCut) Formulation:
  Nodes: 4
  Edges: 5

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

Objective:
  maximize sum_False w[i,j] * (x[i] + x[j] - 2 * x[i] * x[j])

Constraints:
  None (unconstrained binary optimization)

Formulate Model

Create the quantum optimization model.

model = instance.formulate()
model

Model(name=maxcut<maxcut>, sense=Maximize, objective=-6 x_A x_B - 4 x_A x_C - 8 x_B x_C - 2 x_B x_D - 10 x_C x_D + 5 x_A + 8 x_B + 11 x_C + 6 x_D, constraints={})

Solve and Interpret

Solve the model and interpret the solution.

job = SCIP().run(model)
sol = job.result()
mc_sol = instance.interpret(sol)
print(mc_sol.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')













MaxCut Solution:
  Cut Value: 12.0
  Valid: True
  Partition 0: ['A', 'C']
  Partition 1: ['B', 'D']



Plot Solution


Visualize the optimal partition with cut and non-cut edges.


ax = mc_sol.plot(maxcut_data)
plt.show()



png


Model Collections


Generate collections of MaxCut instances using random graphs.


Erdős-Rényi Random Graphs


Generate MaxCut instances using the Erdős-Rényi random graph model with configurable density.


# Generate random Erdős-Rényi graphs with varying density
erdos_renyi_collection = MaxcutCollection.from_random_erdos_renyi(
    min_num_nodes=4,
    max_num_nodes=8,
    min_density=0.3,
    max_density=0.7,
    num_instances=2,
    weighted=True,
    seed=42,
)

print(f"Collection: {erdos_renyi_collection.name}")
print(f"Description: {erdos_renyi_collection.description}")
print(f"Number of instances: {len(erdos_renyi_collection.instances)}")



Collection: Erdős-Rényi MaxCut Set 4-8 nodes
Description: MaxCut instances from Erdős-Rényi random graphs with density range [0.30, 0.70], weighted edges
Number of instances: 10



# Formulate models from the collection
for i, inst in enumerate(erdos_renyi_collection.instances[:3]):
    m = inst.formulate()
    print(f"Instance {i}: {m.name}")



Instance 0: maxcut<maxcut>
Instance 1: maxcut<maxcut>
Instance 2: maxcut<maxcut>



Random Regular Graphs


Generate MaxCut instances using random regular graphs where each node has the same degree.


# Generate random 3-regular graphs (each node has degree 3)
regular_collection = MaxcutCollection.from_random_regular(
    min_num_nodes=6,
    max_num_nodes=10,
    degree=3,
    num_instances=2,
    weighted=True,
    seed=42,
)

print(f"Collection: {regular_collection.name}")
print(f"Description: {regular_collection.description}")
print(f"Number of instances: {len(regular_collection.instances)}")



Collection: 3-Regular MaxCut Set 6-10 nodes
Description: MaxCut instances from 3-regular random graphs, weighted edges
Number of instances: 6



Complete Graphs


Generate MaxCut instances using complete graphs (maximum density - all nodes connected).


# Generate complete graphs (K_n)
complete_collection = MaxcutCollection.from_complete_graph(
    min_num_nodes=4,
    max_num_nodes=7,
    weighted=True,
    seed=42,
)

print(f"Collection: {complete_collection.name}")
print(f"Description: {complete_collection.description}")
print(f"Number of instances: {len(complete_collection.instances)}")

# Example: formulate one model
example_model = complete_collection.instances[0].formulate()
print(f"\nExample model: {example_model.name}")



Collection: Complete Graph MaxCut Set K4-K7
Description: MaxCut instances from complete graphs, weighted edges
Number of instances: 4

Example model: maxcut<maxcut>