MaxWeightMatchingProblem

class MaxWeightMatchingProblem(graph, penalty_scale=10.0, *, max_edges_per_partition=None, partition_algorithm='kernighan_lin', use_classical_cleanup=True, seed=None)

Bases: QAOAProblem

Maximum-weight matching problem for QAOA.

Given a weighted graph, finds a set of edges (matching) that maximizes total weight while ensuring no two selected edges share a node.

Can be used directly with QAOA for small graphs, or with PartitioningProgramEnsemble for large graphs via edge-based partitioning.

Parameters:

• graph (Graph) – Weighted undirected graph.

• penalty_scale (float) – Strength of matching constraint penalties in the QUBO formulation. Higher values enforce constraints more strictly.

• max_edges_per_partition (int | None) – Maximum edges per partition. Setting this enables decompose() for partitioned solving.

• partition_algorithm (Literal['kernighan_lin', 'spectral']) – Edge partitioning strategy. "kernighan_lin" (default, weight-aware) or "spectral".

• use_classical_cleanup (bool) – If True (default), fill unmatched residual nodes via max_weight_matching() during postprocess_candidates().

• seed (int | None) – Random seed for partitioning reproducibility.

Example:

from divi.qprog.problems import MaxWeightMatchingProblem
from divi.qprog import QAOA
from divi.qprog.optimizers import ScipyOptimizer, ScipyMethod
from divi.backends import MaestroSimulator

import networkx as nx

G = nx.gnm_random_graph(8, 12, seed=42)
for u, v in G.edges():
    G[u][v]["weight"] = 1.0

problem = MaxWeightMatchingProblem(G, penalty_scale=10.0)
qaoa = QAOA(problem, n_layers=2,
             optimizer=ScipyOptimizer(method=ScipyMethod.COBYLA),
             max_iterations=20,
             backend=MaestroSimulator())
qaoa.run()

Attributes Summary

cost_hamiltonian	The cost Hamiltonian encoding the optimization objective.
decode_fn	Map a measurement bitstring to a domain-level solution.
graph	The input graph.
loss_constant	Constant offset added back to the expectation value.
mixer_hamiltonian	Mixer Hamiltonian for exploring the solution space.

Methods Summary

compute_energy(bitstring)	Compute matching weight (negated, since lower is better).
decompose()	Decompose this problem into sub-problems for partitioned solving.
evaluate_global_solution(solution)	Score a solution: negative (weight - conflict_penalty * conflicts).
extend_solution(current_solution, prog_id, ...)	Map a sub-solution's decoded bits into the global solution vector.
initial_solution_size()	Size of the global solution vector (e.g. number of graph nodes).
is_feasible(bitstring)	Check that the decoded matching has no node appearing in more than one edge.
postprocess_candidates(candidates, *[, strict])	Post-process matching candidates, optionally hard-filtering invalid ones.

Attributes Documentation

cost_hamiltonian

decode_fn

graph

The input graph.

loss_constant

mixer_hamiltonian

Methods Documentation

compute_energy(bitstring)

Compute matching weight (negated, since lower is better).

Returns None for infeasible bitstrings.

Return type:

float | None

decompose()

Decompose this problem into sub-problems for partitioned solving.

Returns a dict mapping program IDs to sub-problems. Program IDs must be hashable and stable because later partitioning hooks receive the same IDs when extending candidates into a global solution.

Raises:

NotImplementedError – If the subclass does not support decomposition.

Return type:

dict[Hashable, QAOAProblem]

evaluate_global_solution(solution)

Score a solution: negative (weight - conflict_penalty * conflicts).

Lower is better for beam search. Maximizing weight while minimizing conflicts.

Return type:

float

extend_solution(current_solution, prog_id, candidate_decoded)

Map a sub-solution’s decoded bits into the global solution vector.

prog_id is one of the keys returned by decompose(). Must return a new list — do not mutate current_solution.

Return type:

list[int]

initial_solution_size()

Size of the global solution vector (e.g. number of graph nodes).

Return type:

int

is_feasible(bitstring)

Check that the decoded matching has no node appearing in more than one edge.

Return type:

bool

postprocess_candidates(candidates, *, strict=False)

Post-process matching candidates, optionally hard-filtering invalid ones.

With strict=False, invalid raw candidates are repaired and may be improved by classical cleanup. With strict=True, invalid raw candidates are discarded before repair or cleanup.

Return type:

list[tuple[list[tuple], float]]