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	Type	Description
`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:

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`

Format the data as a human-readable string.

Returns:

Type	Description
`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:

Name	Type	Description	Default
`adjacency_matrix`	`ndarray`	Weighted, symmetric adjacency matrix of the graph.	required
`node_names`	`list[int \| str]`	List of node identifiers.	required
`k`	`int`	Number of groups to partition the nodes into. Must be >= 2.	required

Returns:

Type	Description
`MaxKCutData`	The Maximum k-Cut data instance.

Raises:

Type	Description
`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:

Name	Type	Description	Default
`graph`	`Graph`	A NetworkX graph. Edge weights are read from the `"weight"` edge attribute, defaulting to `1.0` when absent.	required
`k`	`int`	Number of groups to partition the nodes into. Must be >= 2.	required

Returns:

Type	Description
`MaxKCutData`	The Maximum k-Cut data instance.

Raises:

Type	Description
`ValueError`	If `k` is less than 2.

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

Name	Type	Description	Default
`n_nodes`	`int`	Number of nodes, by default 6.	`6`
`k`	`int`	Number of groups, by default 3. Must be >= 2.	`3`
`edge_prob`	`float`	Probability of an edge between any two nodes, by default 0.5.	`0.5`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`MaxKCutData`	A randomly generated data instance.

Raises:

Type	Description
`ValueError`	If `k` is less than 2.

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:

Name	Type	Description	Default
`data`	`MaxKCutData`	The problem data.	required

Returns:

Type	Description
`str`	Formatted description of the formulation.

`formulate(data: MaxKCutData) -> Model` `staticmethod`

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

Parameters:

Name	Type	Description	Default
`data`	`MaxKCutData`	The problem data containing the graph structure and number of groups `k`.	required

Returns:

Type	Description
`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:

Name	Type	Description	Default
`solution`	`Solution`	The solver solution.	required
`data`	`MaxKCutData`	The original problem data.	required

Returns:

Type	Description
`MaxKCutSolution`	Structured solution with node-to-group assignment and cut weight.

Raises:

Type	Description
`NoSolutionFoundError`	If the solver did not find any solution.

Solution

Solution model for Maximum k-Cut use case.

`MaxKCutSolution`

Bases: UcSolution

Solution for the Maximum k-Cut use case.

Attributes:

Name	Type	Description
`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:

Name	Type	Description	Default
`data`	`MaxKCutData \| 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`

Format the solution as a human-readable string.

Returns:

Type	Description
`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:

Name	Type	Description	Default
`min_nodes`	`int`	Minimum number of nodes.	required
`max_nodes`	`int`	Maximum number of nodes.	required
`k`	`int`	Number of groups, by default 3.	`3`
`edge_prob`	`float`	Edge probability, by default 0.5.	`0.5`
`num_instances`	`int`	Number of instances per size, by default 1.	`1`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`MaxKCutCollection`	Collection containing generated instances.

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:

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.

Maximum k-Cut API Reference

Data

MaxKCutData

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

to_string() -> str

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

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

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

Formulation

MaxKCutFormulation

to_string(data: MaxKCutData) -> str staticmethod

formulate(data: MaxKCutData) -> Model staticmethod

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

Solution

MaxKCutSolution

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

to_string() -> str

Instance

MaxKCutInstance

Collection

MaxKCutCollection

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

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

`MaxKCutData`

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

`to_string() -> str`

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

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

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

`MaxKCutFormulation`

`to_string(data: MaxKCutData) -> str` `staticmethod`

`formulate(data: MaxKCutData) -> Model` `staticmethod`

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

`MaxKCutSolution`

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

`to_string() -> str`

`MaxKCutInstance`

`MaxKCutCollection`

`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`

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