Skip to content

Max Clique API Reference

Data

Data model for Max Clique use case.

MaxCliqueData

Bases: UcData

Data for the Max Clique use case.

Finds the largest complete subgraph (clique) in a graph.

Attributes:

  • name (Literal['max_clique']) –

    Identifier for this data type.

  • adjacency_matrix (BinAdjMatrix) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    Node identifiers.

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

Plot the Max Clique 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]) -> MaxCliqueData staticmethod

Create MaxCliqueData from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    List of node identifiers.

Returns:

Raises:

  • ValueError –

    If the node_names length doesn't match the matrix, or if node_names contains duplicates.

generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> MaxCliqueData staticmethod

Generate a random Max Clique instance.

Parameters:

  • n_nodes (int, default: 5 ) –

    Number of nodes, by default 5.

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

Examples:

>>> data = MaxCliqueData.generate_random(n_nodes=10, seed=42)

Formulation

Formulation for Max Clique use case.

MaxCliqueFormulation

Bases: UcFormulation[MaxCliqueData, MaxCliqueSolution]

Constraint-based formulation for Max Clique.

Mathematical Formulation 
Decision Variables:
    x_i in {0, 1} -- 1 if node i is in the clique, 0 otherwise.

Objective:
    maximize sum_i x_i

Constraints:
    For each non-edge (i, j): x_i + x_j <= 1

to_string(data: MaxCliqueData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: MaxCliqueData) -> Model staticmethod

Formulate the Max Clique problem as a constraint-based model.

Parameters:

  • data (MaxCliqueData) –

    The problem data containing the graph structure.

Returns:

  • Model –

    A LunaModel ready to be solved.

interpret(solution: Solution, data: MaxCliqueData) -> MaxCliqueSolution staticmethod

Extract a Max Clique solution from the solver result.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (MaxCliqueData) –

    The original problem data.

Returns:

Raises:

Solution

Solution model for Max Clique use case.

MaxCliqueSolution

Bases: UcSolution

Solution for the Max Clique use case.

Attributes:

  • name (Literal['max_clique']) –

    Identifier.

  • clique_nodes (list[int | str]) –

    Nodes in the clique.

  • clique_size (int) –

    Size of the clique.

  • is_valid (bool) –

    Whether all pairs in clique are adjacent.

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

Plot the Max Clique solution on the problem graph.

Clique nodes are highlighted in green; other nodes are grey.

Parameters:

  • data (MaxCliqueData | 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 Max Clique use case.

MaxCliqueInstance

Bases: UcInstance[MaxCliqueData, MaxCliqueFormulation, MaxCliqueSolution]

Instance combining data and formulation for Max Clique.

Collection

Collection of Max Clique instances.

MaxCliqueCollection

Bases: UcInstanceCollection[MaxCliqueInstance]

Collection of Max Clique instances.

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

from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> MaxCliqueCollection classmethod

Generate random Max Clique instances.

Parameters:

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

    Minimum number of nodes.

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

    Maximum number of nodes.

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

  • sizes (Sequence[int] | None, default: None ) –

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

Returns:

Examples:

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