# Weighted set covering
#
# Chooses the cheapest collection of subsets whose union is the whole ground
# set. The element-to-subset incidence is supplied as a parametric set,
# which is the natural encoding when membership is data rather than
# structure.
#
# Technique: Cover each element by summing the indicator of every set that
# contains it, using a parametric set of covering sets per
# element.
#
# On this instance the optimum is 3 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Balas, E. and Padberg, M. W. (1976). Set partitioning: a
# survey. SIAM Review 18(4), 710–760. doi:10.1137/1018115
model m
set S = {1, 2, 3, 4, 5, 6}
set El = {1, 2, 3, 4}
set cov(El) = coveringSets()
const c = {5, 3, 9, 9, 6, 2}, forall s in S
bin x, forall s in S
min sum_{s in S}{c_{s} * x_{s}}
# every element must be covered by at least one chosen subset
constr sum_{s in cov(e)}{x_{s}} >= 1, forall e in El
end
import elytica
def coveringSets():
return {1: [2, 4, 5], 2: [1, 2, 3, 4], 3: [2, 3, 4, 5], 4: [1, 2, 3]}
Read this through MCP: read with path: "formulations/set-cover", or resource hlpl://formulations/set-cover.