Skip to content

Max Independent Set Example

Download Notebook

The Maximum Independent Set problem finds the largest set of vertices in a graph such that no two are adjacent. It is NP-hard and complementary to the minimum vertex cover problem.

import getpass
import os

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

from luna_usecases.max_independent_set import (
    MaxIndependentSetCollection,
    MaxIndependentSetData,
    MaxIndependentSetFormulation,
    MaxIndependentSetInstance,
)

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 graph. An independent set contains no adjacent nodes.

adj = np.array(
    [
        [0, 1, 1, 0, 0],
        [1, 0, 1, 1, 0],
        [1, 1, 0, 0, 1],
        [0, 1, 0, 0, 1],
        [0, 0, 1, 1, 0],
    ]
)
node_names = ["A", "B", "C", "D", "E"]
data = MaxIndependentSetData.from_adjacency_matrix(adjacency_matrix=adj, node_names=node_names)
print(data.to_string())

Max Independent Set Data:
  Nodes: 5
  Edges: 6

Plot Data

Visualize the graph structure.

data.plot()


<Axes: title={'center': 'Max Independent Set — 5 nodes, 6 edges'}>
png

Create Formulation

Maximize selected nodes while ensuring no two are adjacent.

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

Max Independent Set Formulation:
  Nodes: 5
  Edges: 6

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

Objective:
  maximize sum_i x[i]

Constraints:
  1. Edge exclusion (6 constraints):
     x[i] + x[j] <= 1  for all edges (i,j)

Create Instance

Combine data and formulation into a solvable instance.

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

Data:Max Independent Set Data:
  Nodes: 5
  Edges: 6
Formulation:Max Independent Set Formulation:
  Nodes: 5
  Edges: 6

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

Objective:
  maximize sum_i x[i]

Constraints:
  1. Edge exclusion (6 constraints):
     x[i] + x[j] <= 1  for all edges (i,j)

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













Max Independent Set Solution:
  Set size: 2
  Valid: True
  Independent set: ['A', 'D']



Plot Solution


Visualize the optimal solution.


uc_solution.plot(data)



<Axes: title={'center': 'MIS — size=2, valid=True'}>


png


Collections


Generate a benchmark collection of random instances for batch processing.


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



Model: max_independent_set<max_independent_set>
Maximize
  x_0 + x_1 + x_2 + x_3
Subject To
  edge_0_1: x_0 + x_1 <= 1
  edge_0_2: x_0 + x_2 <= 1
  edge_0_3: x_0 + x_3 <= 1
  edge_2_3: x_2 + x_3 <= 1
Binary
  x_0 x_1 x_2 x_3