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(
            arithmetic_eq(model.x[node1], model.x[node2])
            for (node1, node2) in graph.edges

    return model

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

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