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, max_nodes: int, edge_prob: float = 0.5, num_instances: int = 1, *, seed: int | None = None) -> MaxIndependentSetCollection
classmethod
Generate random Max Independent Set instances.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
min_nodes
|
int
|
Minimum number of nodes. |
required |
max_nodes
|
int
|
Maximum number of nodes. |
required |
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
|
Returns:
| Type | Description |
|---|---|
MaxIndependentSetCollection
|
Collection containing generated instances. |