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 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.