# Subset sum
#
# Selects items summing to exactly a target. Degenerate as an optimisation
# problem — the objective is a formality and every feasible point is optimal
# — which makes it the cleanest illustration that a MIP can be a pure
# feasibility question.
#
# Technique: A single equality over binaries: hit the target exactly, with
# no objective to optimise beyond feasibility.
#
# On this instance the optimum is 0 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Karp, R. M. (1972). Reducibility among combinatorial problems.
# Complexity of Computer Computations, 85–103.
model m
set I = {1, 2, 3, 4, 5, 6}
const w = {9, 6, 11, 10, 13, 4}, forall i in I
const t = 23
bin x, forall i in I
# nothing to optimise — any feasible selection is a solution
max sum_{i in I}{0 * x_{i}}
constr sum_{i in I}{w_{i} * x_{i}} = t
end
import elytica
Read this through MCP: read with path: "formulations/subset-sum", or resource hlpl://formulations/subset-sum.