Skip to content

Max Independent Set API Reference

Data

Data model for Max Independent Set use case.

MaxIndependentSetData

Bases: UcData

Data for the Max Independent Set use case.

Finds the largest set of vertices with no two adjacent.

Attributes:

  • name (Literal['max_independent_set']) –

    Identifier.

  • adjacency_matrix (BinAdjMatrix) –

    Symmetric binary adjacency matrix.

  • node_names (list[int | str]) –

    Node identifiers.

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

Plot the Max Independent Set 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 string.

Returns:

  • str –

    String representation of the data.

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

Create a MaxIndependentSetData instance from an adjacency matrix.

Parameters:

  • adjacency_matrix (ndarray) –

    Symmetric binary adjacency matrix representing the graph.

  • node_names (list[int | str]) –

    Node identifiers. Length must match the number of nodes.

Returns:

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

Generate a random graph instance.

Parameters:

  • n_nodes (int, default: 5 ) –

    Number of nodes in the graph, 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 = MaxIndependentSetData.generate_random(n_nodes=5, seed=42)

Formulation

Formulation for Max Independent Set use case.

MaxIndependentSetFormulation

Bases: UcFormulation[MaxIndependentSetData, MaxIndependentSetSolution]

Constraint-based formulation for Max Independent Set.

Decision Variables: x[i] in {0,1} Objective: maximize sum_i x[i] Constraints: For each edge (i,j): x[i] + x[j] <= 1

to_string(data: MaxIndependentSetData) -> str staticmethod

Format the formulation as a string.

Parameters:

Returns:

  • str –

    Formatted description of the formulation.

formulate(data: MaxIndependentSetData) -> Model staticmethod

Formulate the Max Independent Set problem as a constraint model.

Parameters:

Returns:

  • Model –

    The optimization model ready to be solved.

interpret(solution: Solution, data: MaxIndependentSetData) -> MaxIndependentSetSolution staticmethod

Extract solution from solver result.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (MaxIndependentSetData) –

    The original problem data.

Returns:

Raises:

Solution

Solution model for Max Independent Set use case.

MaxIndependentSetSolution

Bases: UcSolution

Solution for Max Independent Set.

Attributes:

  • name (Literal['max_independent_set']) –

    Identifier.

  • independent_set (list[int | str]) –

    Nodes in the independent set.

  • set_size (int) –

    Size of the set.

  • is_valid (bool) –

    No two nodes in set are adjacent.

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

Plot the Max Independent Set solution on the problem graph.

Nodes in the independent set are highlighted.

Parameters:

  • data (MaxIndependentSetData | 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 string.

Returns:

  • str –

    String representation of the solution.

Instance

Instance model for Max Independent Set use case.

MaxIndependentSetInstance

Bases: UcInstance[MaxIndependentSetData, MaxIndependentSetFormulation, MaxIndependentSetSolution]

Instance combining data and formulation for Max Independent Set.

Collection

Collection of Max Independent Set instances.

MaxIndependentSetCollection

Bases: UcInstanceCollection[MaxIndependentSetInstance]

Collection of Max Independent Set instances.

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) -> MaxIndependentSetCollection classmethod

Generate random Max Independent Set 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 ) –

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

  • num_instances (int, default: 1 ) –

    Number of instances per node count, 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:

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: