HLPL / VerTeX Modelling Language Documentation

← formulations

# Set partitioning
#
# Chooses subsets so that every element is covered exactly once — no gaps
# and no overlap. The equality is what separates it from set covering, and
# it is the backbone of crew pairing and rostering, where a duty must be
# flown once rather than at least once.
#
# Technique: Cover every element exactly once: Ax = 1, rather than the Ax
#            >= 1 of covering or the Ax <= 1 of packing.
#
# On this instance the optimum is 12 (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, 7}
set El = {1, 2, 3, 4}
set cov(El) = coveringSets()
const c = {9, 8, 6, 9, 7, 3, 2}, forall s in S

bin x, forall s in S

min sum_{s in S}{c_{s} * x_{s}}

# exactly once — not at least once, and not at most once
constr sum_{s in cov(e)}{x_{s}} = 1, forall e in El
end

import elytica
def coveringSets():
  return {1: [1, 5], 2: [2, 6], 3: [3, 7], 4: [4, 6]}

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