Solve the max-cut problem in Python

Max-cut asks you to split a graph's vertices into two sides so that as many edges as possible cross between them. It is NP-hard, and it is the canonical QUBO / Ising problem — the one quantum annealers are built for. With quicopt you solve that same formulation classically, in a few lines of Python on an ordinary machine.

The naive approach

The usual answers are a greedy or random assignment (fast, but no guarantee on quality), or a QAOA tutorial that needs quantum hardware or a simulator. Max-cut is a binary quadratic problem — so hand it to a solver built for exactly that.

Model it as a QUBO

A binary variable x[i] puts vertex i on side 0 or 1. An edge (i, j) is cut exactly when its endpoints differ, which x[i] + x[j] - 2·x[i]·x[j] captures. Maximize the number of cut edges — a quadratic objective over binaries, no constraints:

maxcut.py

from ortools.math_opt.python import mathopt
from quicopt import Client
edges = [(0,1),(0,2),(1,2),(1,3),(2,3),(2,4),(3,4)]
N = 5
model = mathopt.Model(name="maxcut")
x = [model.add_binary_variable(name=f"x{i}") for i in range(N)]
# each edge contributes 1 to the cut iff its endpoints are on different sides:
model.maximize(sum(x[i] + x[j] - 2 * x[i] * x[j] for (i, j) in edges))
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(model).display)

$ python maxcut.py

├── shots
│   ├── 1 · Heuristic 1   0   0.0s
│   ├── 2 · Heuristic 2   5   0.0s  ◀ best
│   └── 3 · Heuristic 2   5   0.0s
├── status:     heuristic
├── feasible:   n/a
├── objective:  5.0
├── x:          x0=0, x1=1, x2=1, x3=0, x4=1  (5 variables)
└── solve_time: 0.003 s

What you get

quicopt runs several heuristic shots and returns the best: a cut of 5, putting vertices {1, 2, 4} on one side and {0, 3} on the other. For this graph that is the maximum — brute force over all 2⁵ assignments confirms it. Because a QUBO has no constraints to satisfy, the status is heuristic and feasible is n/a.

The point is that the same model scales: on the large public Gset graphs quicopt reaches within a fraction of a percent of the best-known cuts in seconds — see the Gset benchmark — without a GPU or a quantum device.

The problem class behind this: QUBO / Ising
Measured results at scale: Max-cut benchmark (Gset)
Set up the client and solve your first model: Getting started

Reference: M. X. Goemans and D. P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, Journal of the ACM, 1995.

A bigger graph — or a different problem?

Tell us what you're optimizing. We'll help you model it and point you at the right approach.

Talk to us →

Frequently asked questions

Isn't max-cut a quantum-computing problem?

Max-cut is the flagship QUBO/Ising problem that quantum annealers and QAOA target. quicopt solves the exact same formulation classically, on a normal CPU — a classical alternative to a quantum computer, no hardware required.

Is the returned cut optimal?

Max-cut is NP-hard, so quicopt returns a heuristic solution (status: heuristic). For the small graph here it finds a cut of 5 — the maximum, confirmed by brute force. On large graphs it targets best-known quality; see the Gset benchmark.

Is quicopt free to use?

Yes — pip install quicopt and your first call sets up a free key, no license.