# Unbounded knapsack
#
# Packs unlimited copies of each item. Removing the per-item bound from the
# bounded case leaves the capacity constraint as the only thing limiting any
# variable, which is what makes the greedy density heuristic so nearly right
# here and badly wrong in the 0/1 case.
#
# Technique: Integer counts with no per-item limit — only the capacity row
# bounds them.
#
# On this instance the optimum is 20 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Gilmore, P. C. and Gomory, R. E. (1963). A linear programming
# approach to the cutting stock problem — part II. Operations Research
# 11(6), 863–888.
model m
set I = {1, 2, 3, 4}
const v = {5, 10, 10, 8}, forall i in I
const w = {4, 4, 7, 7}, forall i in I
const c = 10
# no per-item bound: only the capacity row limits these
int 0 <= x <= 2, 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-unbounded", or resource hlpl://formulations/knapsack-unbounded.