# Minimum weighted vertex cover
#
# Chooses the cheapest set of vertices touching every edge. Because sets
# hold plain integers, the edge list is a flat index set and incidence is
# supplied by two script functions mapping an edge to its endpoints.
#
# Technique: Address node variables from an edge-indexed constraint via
# endpoint mapping functions: y_{alpha(e)} + y_{beta(e)} >= 1.
#
# On this instance the optimum is 5 (minimisation), 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}
set E = {1, 2, 3, 4}
const w = {1, 6, 3, 1}, forall v in V
bin y, forall v in V
min sum_{v in V}{w_{v} * y_{v}}
# every edge needs at least one of its two endpoints chosen
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: 2}[e]
def beta(e):
return {1: 2, 2: 3, 3: 4, 4: 4}[e]
Read this through MCP: read with path: "formulations/vertex-cover", or resource hlpl://formulations/vertex-cover.