# Maximum cut
#
# Splits vertices into two sides maximising the weight of edges crossing.
# The cut indicator is linearised by two inequalities that together force it
# to zero unless the endpoints differ, which is exact at 0/1 points.
#
# Technique: Partition indicator per vertex plus an edge-cut variable
# sandwiched by z ≤ y_a + y_b and z ≤ 2 − y_a − y_b.
#
# On this instance the optimum is 26 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Barahona, F., Grötschel, M., Jünger, M. and Reinelt, G. (1988).
# An application of combinatorial optimization to statistical physics and
# circuit layout design. Operations Research 36(3), 493–513.
# doi:10.1287/opre.36.3.493
model m
set V = {1, 2, 3, 4, 5}
set E = {1, 2, 3, 4, 5, 6}
const w = {2, 4, 9, 6, 6, 8}, forall e in E
bin y, forall v in V
bin z, forall e in E
max sum_{e in E}{w_{e} * z_{e}}
# z_e can only be 1 when the endpoints fall on opposite sides
constr z_{e} <= y_{alpha(e)} + y_{beta(e)}, forall e in E
constr z_{e} <= 2 - y_{alpha(e)} - y_{beta(e)}, forall e in E
end
import elytica
def alpha(e):
return {1: 1, 2: 2, 3: 3, 4: 4, 5: 2, 6: 3}[e]
def beta(e):
return {1: 2, 2: 3, 3: 4, 4: 5, 5: 4, 6: 5}[e]
Read this through MCP: read with path: "formulations/max-cut", or resource hlpl://formulations/max-cut.