Max Independent Set

import networkx as nx
import pyomo.core as pyo


def mis(graph: nx.Graph) -> pyo.ConcreteModel:
    model = pyo.ConcreteModel()
    model.x = pyo.Var(graph.nodes, domain=pyo.Binary)

    @model.Constraint(graph.edges)
    def independent_rule(model, node1, node2):
        return model.x[node1] + model.x[node2] <= 1

    model.cost = pyo.Objective(expr=sum(model.x.values()), sense=pyo.maximize)

    return model

This function generates a PYOMO model which formulates the Maximum Independent Set problem. The problem concerns finding the largest set of vertices in a graph such that no two vertices are adjacent. The model consists of:

• Index set declarations (model.Nodes, model.Arcs).
• Binary variable declaration for each node (model.x) indicating whether that node is chosen to be included in the set.
• Constraint rule - for each edge we require at least one of the corresponding node variables to be 0.
• Objective rule – the sum of the variables equals to the set size.