Solve the maximum independent set problem in Python

A maximum independent set is the largest possible set of vertices in a graph with no edge between any two of them — the model behind conflict-free scheduling, channel assignment, and de-duplication. It is NP-hard, and the default answer online — a greedy pass — returns a maximal set, not the maximum one. With quicopt you get the proven maximum in a few lines of Python.

The naive approach

A greedy pass grows a set until nothing else fits — a locally-stuck answer that is usually smaller than the true maximum. Enumerating all subsets to find the largest is O(2^n). Model it instead.

Model it as a MILP

A binary variable x[i] selects vertex i. For every edge, at most one endpoint may be chosen. Maximize the number of selected vertices:

from ortools.math_opt.python import mathopt
from quicopt import Client
edges = [(0,1),(0,2),(1,2),(2,3),(3,4),(3,5),(4,5)]
N = 6
model = mathopt.Model(name="mis")
x = [model.add_binary_variable(name=f"x{i}") for i in range(N)]
for (i, j) in edges:                      # no two adjacent vertices both chosen
    model.add_linear_constraint(x[i] + x[j] <= 1)
model.maximize(sum(x))
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(model).display)

├── status:     optimal
├── feasible:   true
├── objective:  2.0
├── x:          x0=0, x1=1, x2=0, x3=1, x4=0, x5=0  (6 variables)
└── solve_time: 0.0171 s

What you get

status: optimal means the solver proved no larger independent set exists — size 2 (vertices {1, 3}). The graph is two triangles joined by an edge, so at most one vertex per triangle can be chosen; the solver finds that bound and proves it, rather than getting stuck like a greedy pass.

The same model scales to large graphs — see how quicopt does on the public QOBLIB independent-set instances in the MIS benchmark.

Next

• The problem class behind this: Mixed-integer linear (MILP)
• The QUBO/Ising view + measured results: MIS benchmark
• Set up the client and solve your first model: Getting started

Reference: R. M. Karp, Reducibility Among Combinatorial Problems, in Complexity of Computer Computations, 1972.