# Maximum weight matching
#
# Selects the heaviest set of edges with no two sharing a vertex. The
# incidence structure is a parametric set mapping each vertex to the edges
# it belongs to, which keeps the constraint one line regardless of graph
# density.
#
# Technique: Degree constraints written over a parametric incidence set
# inc(v), so each vertex bounds the edges touching it.
#
# On this instance the optimum is 10 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Edmonds, J. (1965). Maximum matching and a polyhedron with
# 0,1-vertices. Journal of Research of the National Bureau of Standards B
# 69, 125–130. doi:10.6028/jres.069B.013
model m
set V = {1, 2, 3, 4}
set E = {1, 2, 3}
set inc(V) = incidence()
const w = {7, 8, 3}, forall e in E
bin x, forall e in E
max sum_{e in E}{w_{e} * x_{e}}
# at most one selected edge may touch any given vertex
constr sum_{e in inc(v)}{x_{e}} <= 1, forall v in V
end
import elytica
def incidence():
return {1: [1], 2: [1, 2], 3: [2, 3], 4: [3]}
Read this through MCP: read with path: "formulations/edge-matching", or resource hlpl://formulations/edge-matching.