Minimal Maximal Matching Example

Minimal maximal matching seeks the smallest set of edges in a graph that fulfils two properties:

Matching — A set of edges where no two edges share a vertex.
Maximal — The matching can't be extended; every unselected edge would conflict with an already-selected edge.
Minimal — Among all maximal matchings, pick one with the fewest edges.

Applications include scheduling and resource allocation. For more background, see Matching (graph theory).

import getpass
import os

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

from luna_usecases.minimal_maximal_matching import (
    MinimalMaximalMatchingCollection,
    MinimalMaximalMatchingData,
    MinimalMaximalMatchingFormulation,
    MinimalMaximalMatchingInstance,
)

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. A matching is a set of edges sharing no 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 = MinimalMaximalMatchingData.from_adjacency_matrix(adjacency_matrix=adj, node_names=node_names)
print(data.to_string())

Minimal Maximal Matching Data:
  Nodes: 5
  Edges: 6

Plot Data

Visualize the graph structure.

data.plot()

<Axes: title={'center': 'Minimal Maximal Matching — 5 nodes, 6 edges'}>

Create Formulation

Find a smallest maximal matching — no more edges can be added without sharing a node.

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

Minimal Maximal Matching Formulation:
  Nodes: 5
  Edges: 6

Decision Variables:
  y[i,j] in {0,1} for each edge (i,j)
  y[i,j] = 1 if edge (i,j) is in the matching
  Total: 6 binary variables

Objective:
  minimize sum_e y[e]

Constraints:
  1. Matching (5 constraints):
     sum_{e incident to v} y[e] <= 1  for all nodes v
  2. Maximal (6 constraints):
     sum_{e incident to u or v} y[e] >= 1  for all edges (u,v)

Create Instance

Combine data and formulation into a solvable instance.

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

Data:Minimal Maximal Matching Data:
  Nodes: 5
  Edges: 6
Formulation:Minimal Maximal Matching Formulation:
  Nodes: 5
  Edges: 6

Decision Variables:
  y[i,j] in {0,1} for each edge (i,j)
  y[i,j] = 1 if edge (i,j) is in the matching
  Total: 6 binary variables

Objective:
  minimize sum_e y[e]

Constraints:
  1. Matching (5 constraints):
     sum_{e incident to v} y[e] <= 1  for all nodes v
  2. Maximal (6 constraints):
     sum_{e incident to u or v} y[e] >= 1  for all edges (u,v)

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

2026-05-29 11:35:17 INFO     Sleeping for 5.0 seconds. Waiting and checking a function in a loop.

Minimal Maximal Matching Solution:
  Matching size: 2
  Valid: True
  Matching edges: [('A', 'B'), ('C', 'E')]

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

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

Collections

Generate a benchmark collection of random instances for batch processing.

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

Model: minimal_maximal_matching<minimal_maximal_matching>
Minimize
  y_0_1 + y_0_2 + y_0_3 + y_2_3
Subject To
  matching_0: y_0_1 + y_0_2 + y_0_3 <= 1
  matching_1: y_0_1 <= 1
  matching_2: y_0_2 + y_2_3 <= 1
  matching_3: y_0_3 + y_2_3 <= 1
  maximal_0_1: y_0_1 + y_0_2 + y_0_3 >= 1
  maximal_0_2: y_0_1 + y_0_2 + y_0_3 + y_2_3 >= 1
  maximal_0_3: y_0_1 + y_0_2 + y_0_3 + y_2_3 >= 1
  maximal_2_3: y_0_2 + y_0_3 + y_2_3 >= 1
Binary
  y_0_1 y_0_2 y_0_3 y_2_3