Skip to content

Maximum k-Cut Example

Download Notebook

The Maximum k-Cut problem partitions the nodes of a weighted graph into k groups so that the total weight of edges crossing between different groups is maximized. For k = 2 it reduces to the classic Max-Cut problem. It is NP-hard and has applications in clustering, statistical physics, and VLSI design.

import getpass
import os

import networkx as nx
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.maximum_k_cut import (
    MaxKCutCollection,
    MaxKCutData,
    MaxKCutFormulation,
    MaxKCutInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Build the graph from a NetworkX graph using the from_graph factory. Here we use a 6-node cycle and partition it into k = 3 groups.

graph = nx.cycle_graph(6)
data = MaxKCutData.from_graph(graph, k=3)
print(data.to_string())

Maximum k-Cut Data:
  Nodes: 6
  Edges: 6
  Groups (k): 3

Plot Data

Visualize the weighted graph structure.

data.plot()


<Axes: title={'center': 'Maximum k-Cut — 6 nodes, 6 edges, k=3'}>
png

Create Formulation

Maximize the total weight of edges whose endpoints fall into different groups.

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

Maximum k-Cut Formulation:
  Nodes: 6
  Edges: 6
  Groups (k): 3

Decision Variables:
  x[i,c] in {0,1} for i = 0, ..., 5, c = 0, ..., 2
  x[i,c] = 1 if node i is assigned to group c
  Total: 18 binary variables

Objective:
  maximize sum_{(i,j) in E} w[i,j] * (1 - sum_c x[i,c] * x[j,c])

Constraints:
  1. One group per node (6 constraints):
     sum_c x[i,c] == 1  for all nodes i

Create Instance

Combine data and formulation into a solvable instance.

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

Data:Maximum k-Cut Data:
  Nodes: 6
  Edges: 6
  Groups (k): 3
Formulation:Maximum k-Cut Formulation:
  Nodes: 6
  Edges: 6
  Groups (k): 3

Decision Variables:
  x[i,c] in {0,1} for i = 0, ..., 5, c = 0, ..., 2
  x[i,c] = 1 if node i is assigned to group c
  Total: 18 binary variables

Objective:
  maximize sum_{(i,j) in E} w[i,j] * (1 - sum_c x[i,c] * x[j,c])

Constraints:
  1. One group per node (6 constraints):
     sum_c x[i,c] == 1  for all nodes i

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

Waiting for result | elapsed 0:00:00 | poll 1 | next check in 0.5s

Waiting for result | elapsed 0:00:01 | poll 2 | next check in 1s

Waiting for result | elapsed 0:00:03 | poll 3 | next check in 2s

Waiting for result | elapsed 0:00:05 | poll 4 | next check in 4s

Waiting for result | elapsed 0:00:09 | poll 5 | next check in 8s

Waiting for result | elapsed 0:00:18 | poll 6 | next check in 16s

2026-08-20 12:09:41 INFO     Solve job 'b27cea3b-0b06-4e57-aa8c-d6017bfc1d03' finished with status 'DONE' after    
                             0:00:35.                                                                              

Maximum k-Cut Solution:
  Cut Weight: 6.0
  Groups (k): 3
  Group 0: [0, 2, 4]
  Group 1: []
  Group 2: [1, 3, 5]

Plot Solution

Visualize the partition: nodes are colored by group and cut edges are highlighted.

uc_solution.plot(data)


<Axes: title={'center': 'Maximum k-Cut Solution — k=3, cut weight: 6.0'}>
png

Collections

Generate a benchmark collection of random instances for batch processing.

collection = MaxKCutCollection.from_random(min_nodes=4, max_nodes=6, k=3, num_instances=2, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: maximum_k_cut<s42_n4_k3_i0>
Maximize
  -4 * x_0_0 * x_1_0 - 4 * x_0_0 * x_2_0 - 4 * x_0_1 * x_1_1 - 4 * x_0_1 * x_2_1
  - 4 * x_0_2 * x_1_2 - 4 * x_0_2 * x_2_2 - 10 * x_1_0 * x_3_0
  - 10 * x_1_1 * x_3_1 - 10 * x_1_2 * x_3_2 + 18
Subject To
  assign_0: x_0_0 + x_0_1 + x_0_2 == 1
  assign_1: x_1_0 + x_1_1 + x_1_2 == 1
  assign_2: x_2_0 + x_2_1 + x_2_2 == 1
  assign_3: x_3_0 + x_3_1 + x_3_2 == 1
Binary
  x_0_0 x_0_1 x_0_2 x_1_0 x_1_1 x_1_2 x_2_0 x_2_1 x_2_2 x_3_0 x_3_1 x_3_2