# Counting and cardinality
#
# Selects exactly k items while an auxiliary count tracks how many of a
# distinguished subset were taken, which is then bounded. Counting is a
# plain sum of binaries; no auxiliary machinery is required.
#
# Technique: Constrain how many binaries may be 1 with a single sum, and
# count occurrences by summing indicators.
#
# On this instance the optimum is 10 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Nemhauser, G. L. and Wolsey, L. A. (1988). Integer and
# Combinatorial Optimization. Wiley. doi:10.1002/9781118627372
model m
set I = {1, 2, 3, 4, 5}
set S = {1, 2, 4}
const v = {8, 2, 2, 2, 1}, forall i in I
bin x, forall i in I
max sum_{i in I}{v_{i} * x_{i}}
constr sum_{i in I}{x_{i}} = 2
# at most 1 may come from the restricted subset S
constr sum_{i in S}{x_{i}} <= 1
end
import elytica
Read this through MCP: read with path: "formulations/count-cardinality", or resource hlpl://formulations/count-cardinality.