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 (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:

  • ax (Axes | None, default: None ) –

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

Returns:

  • 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:

  • graph (Graph) –

    A NetworkX graph with optional edge weights.

Returns:

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:

  • adjacency_matrix (ndarray) –

    The weighted adjacency matrix of the graph.

  • node_names (list[str | int]) –

    List of node identifiers.

  • node_position (dict[str, tuple[float, float]] | None, default: None ) –

    Optional positions for visualization.

Returns:

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:

Returns:

  • 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:

  • data (MaxcutData) –

    The MaxCut problem data containing the graph structure.

Returns:

  • Model –

    The quantum optimization model.

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

Interpret the quantum solution.

Parameters:

  • solution (Solution) –

    The quantum solution object.

  • data (MaxcutData) –

    The original MaxCut problem data.

Returns:

  • 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 (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:

  • data (MaxcutData | None, default: None ) –

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

  • ax (Axes | None, default: None ) –

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

Returns:

  • Axes –

    The axes with the plot.

Raises:

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:

  • min_num_nodes (int | None, default: None ) –

    Minimum number of nodes per instance.

  • max_num_nodes (int | None, default: None ) –

    Maximum number of nodes per instance.

  • min_density (float, default: 0.3 ) –

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

  • max_density (float, default: 0.7 ) –

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

  • num_instances (int, default: 1 ) –

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

  • weighted (bool, default: True ) –

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

  • min_weight (float, default: 1.0 ) –

    Minimum edge weight, by default 1.0.

  • max_weight (float, default: 10.0 ) –

    Maximum edge weight, by default 10.0.

  • seed (int | None, default: None ) –

    Random seed for reproducible results, by default None.

  • sizes (Sequence[int] | None, default: 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.

Returns:

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:

  • min_num_nodes (int | None, default: None ) –

    Minimum number of nodes per instance.

  • max_num_nodes (int | None, default: None ) –

    Maximum number of nodes per instance.

  • degree (int, default: 3 ) –

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

  • num_instances (int, default: 1 ) –

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

  • weighted (bool, default: True ) –

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

  • min_weight (float, default: 1.0 ) –

    Minimum edge weight, by default 1.0.

  • max_weight (float, default: 10.0 ) –

    Maximum edge weight, by default 10.0.

  • seed (int | None, default: None ) –

    Random seed for reproducible results, by default None.

  • sizes (Sequence[int] | None, default: 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.

Returns:

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:

  • min_num_nodes (int | None, default: None ) –

    Minimum number of nodes per instance.

  • max_num_nodes (int | None, default: None ) –

    Maximum number of nodes per instance.

  • weighted (bool, default: True ) –

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

  • min_weight (float, default: 1.0 ) –

    Minimum edge weight, by default 1.0.

  • max_weight (float, default: 10.0 ) –

    Maximum edge weight, by default 10.0.

  • seed (int | None, default: None ) –

    Random seed for reproducible results, by default None.

  • sizes (Sequence[int] | None, default: 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.

Returns:

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:

  • max_runtime (float, default: 3600 ) –

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

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • 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: