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 | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
to_string() -> str
from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str]) -> MaxIndependentSetData
staticmethod
Create a MaxIndependentSetData instance from an adjacency matrix.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
adjacency_matrix
|
ndarray
|
Symmetric binary adjacency matrix representing the graph. |
required |
node_names
|
list[int | str]
|
Node identifiers. Length must match the number of nodes. |
required |
Returns:
| Type | Description |
|---|---|
MaxIndependentSetData
|
The Max Independent Set data instance. |
generate_random(n_nodes: int = 5, edge_prob: float = 0.5, seed: int | None = None) -> MaxIndependentSetData
staticmethod
Generate a random graph instance.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n_nodes
|
int
|
Number of nodes in the graph, by default 5. |
5
|
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 |
|---|---|
MaxIndependentSetData
|
A randomly generated data instance. |
Examples:
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
MaxIndependentSetData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
str
|
Formatted description of the formulation. |
formulate(data: MaxIndependentSetData) -> Model
staticmethod
Formulate the Max Independent Set problem as a constraint model.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
MaxIndependentSetData
|
The problem data containing the graph structure. |
required |
Returns:
| Type | Description |
|---|---|
Model
|
The optimization model ready to be solved. |
interpret(solution: Solution, data: MaxIndependentSetData) -> MaxIndependentSetSolution
staticmethod
Extract solution from solver result.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The solver solution. |
required |
data
|
MaxIndependentSetData
|
The original problem data. |
required |
Returns:
| Type | Description |
|---|---|
MaxIndependentSetSolution
|
Structured solution with metrics. |
Raises:
| Type | Description |
|---|---|
NoSolutionFoundError
|
If no feasible solution was found. |
Solution
Solution model for Max Independent Set use case.
MaxIndependentSetSolution
Bases: UcSolution
Solution for Max Independent Set.
Attributes:
| Name | Type | Description |
|---|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
MaxIndependentSetData | None
|
Problem data used to reconstruct the graph. Required --
a |
None
|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
Raises:
| Type | Description |
|---|---|
ValueError
|
If data is |
to_string() -> str
Format the solution as a string.
Returns:
| Type | Description |
|---|---|
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:
| Name | Type | Description | Default |
|---|---|---|---|
min_nodes
|
int | None
|
Minimum number of nodes. |
None
|
max_nodes
|
int | None
|
Maximum number of nodes. |
None
|
edge_prob
|
float
|
Probability of an edge between any two nodes, by default 0.5. |
0.5
|
num_instances
|
int
|
Number of instances per node count, by default 1. |
1
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
sizes
|
Sequence[int] | None
|
Explicit sizes to generate, e.g. |
None
|
Returns:
| Type | Description |
|---|---|
MaxIndependentSetCollection
|
Collection containing generated instances. |
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: |
Raises:
| Type | Description |
|---|---|
ValueError
|
If |