# Maximum weighted independent set
#
# Selects the heaviest set of mutually non-adjacent vertices. Uses the same
# edge-to-endpoint mapping as vertex cover with the inequality reversed,
# which is the standard complementary formulation.
#
# Technique: The complement pattern of vertex cover: y_{alpha(e)} +
# y_{beta(e)} <= 1 forbids both endpoints of any edge.
#
# On this instance the optimum is 14 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Nemhauser, G. L. and Trotter, L. E. (1975). Vertex packings:
# structural properties and algorithms. Mathematical Programming 8, 232–248.
# doi:10.1007/BF01580444
model m
set V = {1, 2, 3, 4, 5}
set E = {1, 2, 3, 4, 5}
const w = {6, 6, 6, 1, 8}, forall v in V
bin y, forall v in V
max sum_{v in V}{w_{v} * y_{v}}
# no edge may have both endpoints selected
constr y_{alpha(e)} + y_{beta(e)} <= 1, forall e in E
end
import elytica
def alpha(e):
return {1: 1, 2: 2, 3: 3, 4: 4, 5: 3}[e]
def beta(e):
return {1: 2, 2: 3, 3: 4, 4: 5, 5: 5}[e]
Read this through MCP: read with path: "formulations/independent-set", or resource hlpl://formulations/independent-set.