Skip to content

Maximum k-Cut API Reference

Data

Data model for Maximum k-Cut use case.

MaxKCutData

Bases: UcData

Data for the Maximum k-Cut use case.

The Maximum k-Cut problem partitions the nodes of a weighted graph into k groups so that the total weight of edges whose endpoints fall into different groups is maximized. For k = 2 this reduces to the classic Maximum Cut problem. The problem is NP-hard and has applications in clustering, statistical physics, and network analysis.

Attributes:

  • name (Literal['maximum_k_cut']) –

    A constant identifier for this data type, always set to "maximum_k_cut". Used for registration and type identification.

  • adjacency_matrix (AdjMatrix) –

    A 2D NumPy array representing the weighted, symmetric adjacency matrix of the graph. The element at [i, j] is the weight of the edge between node i and node j. Shape must be (n_nodes, n_nodes) where n_nodes = len(node_names). Diagonal elements must be 0 (no self-loops).

  • node_names (list[int | str]) –

    A list of node identifiers. The order corresponds to the rows/columns of adjacency_matrix.

  • k (int) –

    The number of groups (colors) into which the nodes are partitioned. Must be at least 2.

Examples:

>>> data = MaxKCutData(
...     adjacency_matrix=np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]]),
...     node_names=[0, 1, 2],
...     k=3,
... )

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

Plot the Maximum k-Cut graph instance.

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

Format the data as a human-readable string.

Returns:

  • str –

    String representation of the data.

from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str], k: int) -> MaxKCutData staticmethod

Create MaxKCutData from a weighted adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Weighted, symmetric adjacency matrix of the graph.

  • node_names (list[int | str]) –

    List of node identifiers.

  • k (int) –

    Number of groups to partition the nodes into. Must be >= 2.

Returns:

Raises:

  • ValueError –

    If k is less than 2, if node_names length does not match the matrix size, or if node_names contains duplicates.

from_graph(graph: nx.Graph, k: int) -> MaxKCutData staticmethod

Create MaxKCutData from a NetworkX graph.

Parameters:

  • graph (Graph) –

    A NetworkX graph. Edge weights are read from the "weight" edge attribute, defaulting to 1.0 when absent.

  • k (int) –

    Number of groups to partition the nodes into. Must be >= 2.

Returns:

Raises:

generate_random(n_nodes: int = 6, k: int = 3, edge_prob: float = 0.5, seed: int | None = None) -> MaxKCutData staticmethod

Generate a random Maximum k-Cut instance.

Parameters:

  • n_nodes (int, default: 6 ) –

    Number of nodes, by default 6.

  • k (int, default: 3 ) –

    Number of groups, by default 3. Must be >= 2.

  • edge_prob (float, default: 0.5 ) –

    Probability of an edge between any two nodes, by default 0.5.

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

    Random seed for reproducibility, by default None.

Returns:

Raises:

Examples:

>>> data = MaxKCutData.generate_random(n_nodes=6, k=3, seed=42)

Formulation

Formulation for Maximum k-Cut use case.

MaxKCutFormulation

Bases: UcFormulation[MaxKCutData, MaxKCutSolution]

Constraint-based formulation for Maximum k-Cut.

Mathematical Formulation 
Symbols:
    n      -- number of nodes in the graph.
    k      -- number of groups (colors), with k >= 2.
    E      -- set of undirected edges (i, j) with i < j.
    w_{ij} -- weight of edge (i, j).

Decision Variables:
    x_{i,c} in {0, 1} -- 1 if node i is assigned to group c, 0 otherwise,
    for i = 0, ..., n - 1 and c = 0, ..., k - 1.

Objective (maximize):
    maximize sum_{(i,j) in E} w_{ij} * (1 - sum_{c} x_{i,c} * x_{j,c})

    The inner term ``sum_{c} x_{i,c} * x_{j,c}`` equals 1 when nodes i and j
    share a group and 0 otherwise, so each edge contributes its weight
    exactly when its endpoints fall in different groups.

Constraints:
    Each node belongs to exactly one group:
        sum_{c} x_{i,c} == 1  for all i = 0, ..., n - 1.

to_string(data: MaxKCutData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: MaxKCutData) -> Model staticmethod

Formulate the Maximum k-Cut problem as a constraint-based model.

Parameters:

  • data (MaxKCutData) –

    The problem data containing the graph structure and number of groups k.

Returns:

  • Model –

    A Luna Model ready to be solved.

interpret(solution: Solution, data: MaxKCutData) -> MaxKCutSolution staticmethod

Extract a Maximum k-Cut solution from the solver result.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (MaxKCutData) –

    The original problem data.

Returns:

  • MaxKCutSolution –

    Structured solution with node-to-group assignment and cut weight.

Raises:

Solution

Solution model for Maximum k-Cut use case.

MaxKCutSolution

Bases: UcSolution

Solution for the Maximum k-Cut use case.

Attributes:

  • name (Literal['maximum_k_cut']) –

    Identifier for this solution type, always "maximum_k_cut".

  • assignment (dict[int | str, int]) –

    Mapping from each node to its assigned group index (0 to k - 1).

  • cut_weight (float) –

    Total weight of edges whose endpoints lie in different groups. This is the objective value that was maximized.

  • k (int) –

    The number of groups the nodes were partitioned into.

Examples:

>>> solution = MaxKCutSolution(
...     assignment={0: 0, 1: 1, 2: 2},
...     cut_weight=3.0,
...     k=3,
... )

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

Plot the Maximum k-Cut solution on the problem graph.

Nodes are colored by their assigned group, and cut edges (endpoints in different groups) are highlighted.

Parameters:

  • data (MaxKCutData | 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

Format the solution as a human-readable string.

Returns:

  • str –

    String representation of the solution.

Instance

Instance model for Maximum k-Cut use case.

MaxKCutInstance

Bases: UcInstance[MaxKCutData, MaxKCutFormulation, MaxKCutSolution]

Instance combining data and formulation for Maximum k-Cut.

Collection

Collection of Maximum k-Cut instances.

MaxKCutCollection

Bases: UcInstanceCollection[MaxKCutInstance]

Collection of Maximum k-Cut instances.

This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.

from_random(min_nodes: int, max_nodes: int, k: int = 3, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> MaxKCutCollection classmethod

Generate random Maximum k-Cut instances.

Parameters:

  • min_nodes (int) –

    Minimum number of nodes.

  • max_nodes (int) –

    Maximum number of nodes.

  • k (int, default: 3 ) –

    Number of groups, by default 3.

  • edge_prob (float, default: 0.5 ) –

    Edge probability, by default 0.5.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

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

    Random seed for reproducibility, by default None.

Returns:

Examples:

>>> collection = MaxKCutCollection.from_random(
...     min_nodes=5,
...     max_nodes=7,
...     k=3,
...     num_instances=2,
...     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: