# 0/1 knapsack
#
# Selects a subset of items maximising value within a weight budget. The
# canonical single-constraint integer program and the base case every other
# packing formulation specialises.
#
# Technique: One binary per item, a single capacity row.
#
# On this instance the optimum is 51 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Dantzig, G. B. (1957). Discrete-variable extremum problems.
# Operations Research 5(2), 266–277. doi:10.1287/opre.5.2.266
model m
set I = {1, 2, 3, 4, 5, 6, 7}
const v = {12, 15, 1, 15, 1, 19, 3}, forall i in I
const w = {7, 2, 2, 5, 2, 5, 11}, forall i in I
const c = 16
bin x, forall i in I
max sum_{i in I}{v_{i} * x_{i}}
constr sum_{i in I}{w_{i} * x_{i}} <= c
end
import elytica
Read this through MCP: read with path: "formulations/knapsack-01", or resource hlpl://formulations/knapsack-01.