Skip to content

Maximum Cut Problem (MaxCut) API Reference

Data

Data model for Maxcut use case.

MaxcutData

Bases: UcData

Data for the Maximum Cut (MaxCut) use case.

This class encapsulates all necessary information to define and solve a MaxCut instance. The MaxCut problem is a classic combinatorial optimization problem where the goal is to partition the vertices of a graph into two sets such that the total weight of edges between the two sets is maximized.

The MaxCut problem is NP-hard and has applications in statistical physics, circuit design, clustering, and network analysis.

Attributes:

Name Type Description
name Literal['maxcut']

A constant identifier for this data type, always set to "maxcut". Used for registration and type identification in the use case registry.
node_names list[str | int]

A list of node identifiers (strings or integers) representing all nodes in the graph. The order in this list corresponds to rows/columns in the adjacency_matrix. Example: ["A", "B", "C", "D"] or [0, 1, 2, 3]
adjacency_matrix AdjMatrix

A 2D NumPy array representing the weighted adjacency matrix of the graph. The element at [i, j] represents the weight of the edge between node i and node j. For undirected graphs, this matrix is symmetric. Shape must be (n_nodes, n_nodes) where n_nodes = len(node_names). Diagonal elements should be 0 (no self-loops).
node_position (dict[str, tuple[float, float]] | None, optional)

Optional dictionary mapping each node identifier to its (x, y) coordinates in 2D space. Useful for:

  • Visualizing the graph instance and its solution
  • Spatial analysis of the partition
  • Plotting the cut

If None, positions are not available for visualization. Example: {"A": (0.0, 0.0), "B": (1.0, 0.0), "C": (0.5, 0.87)}

Examples:

Create a simple 4-node MaxCut instance:

>>> maxcut = MaxcutData(
...     name="maxcut",
...     node_names=["A", "B", "C", "D"],
...     adjacency_matrix=np.array([[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]),
...     node_position={"A": (0, 0), "B": (1, 0), "C": (1, 1), "D": (0, 1)},
... )

plot(*, ax: Axes | None = None) -> Axes

Plot the MaxCut graph instance.

Draws nodes and weighted edges using NetworkX. Node positions are taken from node_position when available, otherwise computed via nx.spring_layout.

Parameters:

Name Type Description Default
ax Axes | None

Matplotlib axes to draw on. Creates a new figure if None.

 None

Returns:

Type Description
Axes

The axes with the plot.

to_string() -> str

Print the data.

from_graph(graph: nx.Graph) -> MaxcutData staticmethod

Create MaxcutData from a NetworkX graph.

Parameters:

Name Type Description Default
graph Graph

A NetworkX graph with optional edge weights.

 required

Returns:

Type Description
MaxcutData

The MaxCut data instance.

from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str], node_position: dict[str, tuple[float, float]] | None = None) -> MaxcutData staticmethod

Create MaxcutData from an adjacency matrix.

Parameters:

Name Type Description Default
adjacency_matrix ndarray

The weighted adjacency matrix of the graph.

 required
node_names list[str | int]

List of node identifiers.

 required
node_position dict[str, tuple[float, float]] | None

Optional positions for visualization.

 None

Returns:

Type Description
MaxcutData

The MaxCut data instance.

Formulation

Formulation for Maxcut use case.

MaxcutFormulation

Bases: UcFormulation[MaxcutData, MaxcutSolution]

Formulation for the Maximum Cut (MaxCut) use case.

This formulation creates a QUBO (Quadratic Unconstrained Binary Optimization) model for the MaxCut problem. Each node is assigned a binary variable (0 or 1) representing which partition it belongs to.

The objective is to maximize the total weight of edges between the two partitions.

to_string(data: MaxcutData) -> str staticmethod

Format the formulation as a string.

Parameters:

Name Type Description Default
data MaxcutData

The MaxCut problem data.

 required

Returns:

Type Description
str

Formatted description of the MaxCut formulation.

formulate(data: MaxcutData) -> Model staticmethod

Formulate the MaxCut problem as a quantum optimization model.

The MaxCut problem is formulated as a QUBO where we want to maximize: sum_{i<j} w_{ij} * (x_i + x_j - 2x_ix_j)

This equals the sum of edge weights where endpoints are in different partitions.

Parameters:

Name Type Description Default
data MaxcutData

The MaxCut problem data containing the graph structure.

 required

Returns:

Type Description
Model

The quantum optimization model.

interpret(solution: Solution, data: MaxcutData) -> MaxcutSolution staticmethod

Interpret the quantum solution.

Parameters:

Name Type Description Default
solution Solution

The quantum solution object.

 required
data MaxcutData

The original MaxCut problem data.

 required

Returns:

Type Description
MaxcutSolution

The interpreted MaxCut solution with partition and cut value.

Solution

Solution model for Maxcut use case.

MaxcutSolution

Bases: UcSolution

Solution for the Maximum Cut (MaxCut) use case.

This class represents a solution to the MaxCut problem, which partitions the nodes of a graph into two sets to maximize the total weight of edges between the two sets.

Attributes:

Name Type Description
name Literal['maxcut']

A constant identifier for this solution type, always set to "maxcut".
partition dict[str | int, int]

A dictionary mapping each node to its partition (0 or 1). Nodes in partition 0 are in one set, nodes in partition 1 are in the other. Example: {"A": 0, "B": 1, "C": 0, "D": 1} means nodes A and C are in one set, while B and D are in the other.
cut_value float

The total weight of edges crossing between the two partitions. This is the objective value that was maximized.
is_valid bool

Whether the solution is valid (all nodes are assigned to a partition).

Examples:

>>> solution = MaxcutSolution(
...     name="maxcut",
...     partition={"A": 0, "B": 1, "C": 0, "D": 1},
...     cut_value=5.0,
...     is_valid=True,
... )

plot(data: MaxcutData | None = None, *, ax: Axes | None = None) -> Axes

Plot the MaxCut solution on the problem graph.

Nodes are colored by partition assignment and edges are colored to distinguish cut edges from non-cut edges.

Parameters:

Name Type Description Default
data MaxcutData | None

Problem data used to reconstruct the graph. Required -- a ValueError is raised when None.

 None
ax Axes | None

Matplotlib axes to draw on. Creates a new figure if None.

 None

Returns:

Type Description
Axes

The axes with the plot.

Raises:

Type Description
ValueError

If data is None.

to_string() -> str

Print the solution.

Instance

Instance model for Maxcut use case.

MaxcutInstance

Bases: UcInstance[MaxcutData, MaxcutFormulation, MaxcutSolution]

Instance combining data and formulation for Maxcut.

Collection

Collection of Maxcut instances.

MaxcutCollection

Bases: UcInstanceCollection[MaxcutInstance]

Collection of MaxCut instances generated from random graphs.

This collection provides methods to generate random graph instances for the MaxCut problem using various NetworkX graph models.

from_random_erdos_renyi(min_num_nodes: int | None = None, max_num_nodes: int | None = None, min_density: float = 0.3, max_density: float = 0.7, num_instances: int = 1, *, sizes: Sequence[int] | None = None, weighted: bool = True, min_weight: float = 1.0, max_weight: float = 10.0, seed: int | None = None) -> MaxcutCollection classmethod

Generate MaxCut instances using Erdős-Rényi random graphs.

The Erdős-Rényi model creates a graph by connecting each pair of nodes with a probability (density). This is one of the most common random graph models.

Parameters:

Name Type Description Default
min_num_nodes int | None

Minimum number of nodes per instance.

 None
max_num_nodes int | None

Maximum number of nodes per instance.

 None
min_density float

Minimum edge probability (graph density), by default 0.3. Must be between 0 and 1.

 0.3
max_density float

Maximum edge probability (graph density), by default 0.7. Must be between 0 and 1.

 0.7
num_instances int

Number of instances to generate for each node count, by default 1.

 1
weighted bool

Whether to add random weights to edges, by default True. If False, all edges have weight 1.

 True
min_weight float

Minimum edge weight, by default 1.0.

 1.0
max_weight float

Maximum edge weight, by default 10.0.

 10.0
seed int | None

Random seed for reproducible results, by default None.

 None
sizes Sequence[int] | None

Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_num_nodes/max_num_nodes, by default None.

 None

Returns:

Type Description
MaxcutCollection

Collection containing generated MaxCut instances.

Examples:

>>> collection = MaxcutCollection.from_random_erdos_renyi(
...     min_num_nodes=5,
...     max_num_nodes=10,
...     min_density=0.3,
...     max_density=0.7,
...     num_instances=3,
...     seed=42,
... )

from_random_regular(min_num_nodes: int | None = None, max_num_nodes: int | None = None, degree: int = 3, num_instances: int = 1, *, sizes: Sequence[int] | None = None, weighted: bool = True, min_weight: float = 1.0, max_weight: float = 10.0, seed: int | None = None) -> MaxcutCollection classmethod

Generate MaxCut instances using random regular graphs.

A random regular graph is a graph where every node has exactly the same degree (number of connections). This creates more structured instances compared to Erdős-Rényi graphs.

Parameters:

Name Type Description Default
min_num_nodes int | None

Minimum number of nodes per instance.

 None
max_num_nodes int | None

Maximum number of nodes per instance.

 None
degree int

Degree of each node (must be less than num_nodes), by default 3.

 3
num_instances int

Number of instances to generate for each node count, by default 1.

 1
weighted bool

Whether to add random weights to edges, by default True.

 True
min_weight float

Minimum edge weight, by default 1.0.

 1.0
max_weight float

Maximum edge weight, by default 10.0.

 10.0
seed int | None

Random seed for reproducible results, by default None.

 None
sizes Sequence[int] | None

Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_num_nodes/max_num_nodes, by default None.

 None

Returns:

Type Description
MaxcutCollection

Collection containing generated MaxCut instances.
Notes

For a regular graph to exist, n * degree must be even and degree < n.

Examples:

>>> collection = MaxcutCollection.from_random_regular(
...     min_num_nodes=6,
...     max_num_nodes=10,
...     degree=3,
...     num_instances=2,
...     seed=42,
... )

from_complete_graph(min_num_nodes: int | None = None, max_num_nodes: int | None = None, *, sizes: Sequence[int] | None = None, weighted: bool = True, min_weight: float = 1.0, max_weight: float = 10.0, seed: int | None = None) -> MaxcutCollection classmethod

Generate MaxCut instances using complete graphs.

A complete graph has an edge between every pair of nodes. These are the densest possible graphs and provide challenging MaxCut instances.

Parameters:

Name Type Description Default
min_num_nodes int | None

Minimum number of nodes per instance.

 None
max_num_nodes int | None

Maximum number of nodes per instance.

 None
weighted bool

Whether to add random weights to edges, by default True.

 True
min_weight float

Minimum edge weight, by default 1.0.

 1.0
max_weight float

Maximum edge weight, by default 10.0.

 10.0
seed int | None

Random seed for reproducible results, by default None.

 None
sizes Sequence[int] | None

Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_num_nodes/max_num_nodes, by default None.

 None

Returns:

Type Description
MaxcutCollection

Collection containing generated MaxCut instances.

Examples:

>>> collection = MaxcutCollection.from_complete_graph(
...     min_num_nodes=4,
...     max_num_nodes=8,
...     weighted=True,
...     seed=42,
... )

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

Name Type Description Default
max_runtime float

SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

 3600
quiet bool

Suppress the SCIP solver output.

 True

Returns:

Type Description
list[bool]

Feasibility mask over the instances as they were before filtering, in that order: True where the instance was kept, False where it was removed.

Raises:

Type Description
ValueError

If max_runtime is not positive.