HLPL / VerTeX Modelling Language Documentation

← formulations

# Minimum spanning tree
#
# Connects every vertex at least total cost. The cardinality row alone would
# allow a forest plus a cycle, so the subset rows are what force acyclicity
# — the same family DFJ uses for tours, applied to trees. The LP relaxation
# of this description is integral, which is why a greedy algorithm solves it
# exactly.
#
# Technique: Pick exactly |V| - 1 edges and forbid a cycle in every subset:
#            edges inside S number at most |S| - 1.
#
# On this instance the optimum is 13 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Edmonds, J. (1971). Matroids and the greedy algorithm.
# Mathematical Programming 1(1), 127–136.
model m
set V = {1, 2, 3, 4}
set E = {1, 2, 3, 4, 5, 6}
set K = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
const w = {2, 8, 3, 12, 6, 14}, forall e in E
const inside = {{1, 0, 0, 0, 0, 0},
           {0, 1, 0, 0, 0, 0},
           {0, 0, 0, 1, 0, 0},
           {1, 1, 0, 1, 0, 0},
           {0, 0, 1, 0, 0, 0},
           {0, 0, 0, 0, 1, 0},
           {1, 0, 1, 0, 1, 0},
           {0, 0, 0, 0, 0, 1},
           {0, 1, 1, 0, 0, 1},
           {0, 0, 0, 1, 1, 1}}, forall k in K, forall e in E
const sz = {2, 2, 2, 3, 2, 2, 3, 2, 3, 3}, forall k in K

bin x, forall e in E

min sum_{e in E}{w_{e} * x_{e}}

# a spanning tree on n vertices has exactly n - 1 edges
constr sum_{e in E}{x_{e}} = 3
# no subset may hold enough edges to contain a cycle
constr sum_{e in E}{inside_{k,e} * x_{e}} <= sz_{k} - 1, forall k in K
end

import elytica

Read this through MCP: read with path: "formulations/spanning-tree", or resource hlpl://formulations/spanning-tree.