MaxCut

import networkx as nx
import pyomo.core as pyo


def arithmetic_eq(x1: int, x2: int) -> int:
    return x1 * x2 + (1 - x1) * (1 - x2)


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

    model.cost = pyo.Objective(
        expr=sum(
            arithmetic_eq(model.x[node1], model.x[node2])
            for (node1, node2) in graph.edges
        ),
        sense=pyo.minimize,
    )

    return model

This function generates a PYOMO model that formulates the Max-Cut problem. The problem finds a partition of the graph vertices to two complementary sets such that the number of edges between the sets is maximal. The model contains:

• Binary variable declaration for each node (model.x) indicating to which set the vertex belongs.
• Objective rule – the sum of crossing edges.