# Bounded knapsack
#
# Packs multiple copies of each item, up to a per-item limit. The only
# structural change from the 0/1 case is the variable type and its bound;
# the capacity row is identical, which is why the bounded case is usually
# presented as a variant rather than a separate problem.
#
# Technique: Integer counts with per-item upper bounds instead of binaries
# — int 0 <= x <= b_i rather than bin x.
#
# On this instance the optimum is 46 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Martello, S. and Toth, P. (1990). Knapsack Problems: Algorithms
# and Computer Implementations. Wiley.
model m
set I = {1, 2, 3}
const v = {10, 11, 7}, forall i in I
const w = {5, 1, 2}, forall i in I
const b = {1, 2, 2}, forall i in I
const c = 16
int 0 <= x <= 2, forall i in I
max sum_{i in I}{v_{i} * x_{i}}
# per-item copy limit
constr x_{i} <= b_{i}, forall i in I
constr sum_{i in I}{w_{i} * x_{i}} <= c
end
import elytica
Read this through MCP: read with path: "formulations/knapsack-bounded", or resource hlpl://formulations/knapsack-bounded.